Home / Questions / 305341
Accepted
RazerJs
Asked: 2020-11-02 12:36:36 +0800 CST 2020-11-02 12:36:36 +0800 CST

improve speed of O(n^2) in nested for for combination search

  • 772

I was doing this problem that consists of given some entries of an array of integers and a number n .. find all the pairs of elements in the array that are equal to n and if there are several pairs choose the closest pair to the left .. Ex:

arr=[10, 5, 2, 3, 7, 5], n=10

       ^--------^ [5,5] 5+5=10
           ^--^   [3,7] 3+7=10 *mas cercano a la izquierda

result = [3,7]

This is one of the simplest examples of using nested for to test all combinations of two elements in an array (binary search)... This is my solution...

var sum_pairs = function (ints, s) {
    let min = Number.MAX_SAFE_INTEGER;
    let resp = []
    for (let i = 0; i < ints.length - 1; i++)
        for (let j = i + 1; j < ints.length; j++)
            if ((ints[i] + ints[j] == s) && (j < min)) {
                resp.push([ints[i], ints[j]]), min = j;
            }
    return (resp.length == 1) ? resp[0] : (resp.length > 1) ? resp[resp.length - 1] : undefined
}


console.log(sum_pairs([10, 5, 2, 3, 7, 5], 10));
console.log(sum_pairs([4, 3, 2, 3, 4], 6));

it goes through the array looking for all the combinations of the first number, if they add up to n and its second number (j) is further to the left of the min it adds it to the array resp[]... if it finds a single solution it returns resp[]else and there are several pairs it returns the last element en resp[](which therefore was more to the left)... if it doesn't find any pairs, it returns undefined ... it does what the problem asks for and it was more complex, I summarized it because it didn't pass the speed tests... but it's still O (n^2)... I would like to know how to improve its complexity or how to make a faster solution for this type of problem...

javascript

2 Answers

  1. Best Answer

    The trick of only using one iteration is to know the values ​​that existed before, in this case I recommend Map .

    In this example we will use it to store in its key the value of the array and the value its position.

    Once this is clear, when we iterate we only have to calculate the difference s with respect to the number that is being consulted and validate if this value exists in the Map

    let numeroFaltante = s - ints[i];   
numeroEncontrado = numbers.get(numeroFaltante);

    All the code below:

    var sum_pairs = function (ints, s) {
    const numbers = new Map();
    numbers.set(ints[0],0);
    const combinacion = {
      numeros: [],
      diferencia: 99
    };
    
    for (let i = 1; i < ints.length ; i++){

      let numeroFaltante = s - ints[i];
      numeroEncontrado = numbers.get(numeroFaltante);
   
      if(numeroEncontrado >= 0){
        let diferencia = i - numeroEncontrado;
        if (combinacion.diferencia > diferencia){
          combinacion.numeros = [numeroFaltante , ints[i]];
          combinacion.diferencia = diferencia;
        
        }
      }
      numbers.set(ints[i],i)
    }
    return combinacion.numeros;
}


console.log(sum_pairs([10, 5, 2, 3, 7, 5], 10));
console.log(sum_pairs([4, 3, 2, 3, 4], 6));
console.log(sum_pairs([4,-2,3,3,4] , 8));
console.log(sum_pairs([1, 4, 8, 7, 3, 15], 8));

    • 5

  2. The main problem of the first solution with (nested for); It happens when the pairs must be searched in a very large array... because in this way we are looking for all the combinations of the first element, then those of the second element, third element... and you can't stop when you find the first pair, because there is the other condition that you must return the closest pair to the left... there the speed test fails. A fairly simple way is to use the technique from jacknavarow's answer above along with memoisation..

    let sum_pairsUp = (a, n) => {
    let memoisation = {}
    for (x of a) {
        if (memoisation[n - x])
            return [n - x, x]
        else
            memoisation[x] = 1
    }
}

console.log(sum_pairsUp([12, 4, 1,2,34,12,2,6,2,8,36, 7, 3, 15], 10));
console.log(sum_pairsUp([1, 4, 1, 7, 3, 15], 2)); //para repetidos
console.log(sum_pairsUp([1, 4, 1, 7, 3, 15], 25));

    • 1