Given an array of integers, return all pairs that add up to 100

Question

I was recently given this programming challenge on an interview, and I decided to use javascript to solve it. I did, but I'm not happy with my implementation. I can't help thinking there must be a better way of doing this.

The exercise goes like this:

Given an array of integers, write a function that returns an array of each pair of integers that add up to 100. The input is

[0, 1, 100, 99, 0, 10, 90, 30, 55, 33, 55, 75, 50, 51, 49, 50, 51, 49, 51]

and the function should return something like this (the order is not important).

[ [0,100], [1,99], [10,90], [50,50], [49,51] ]

My implementation looks like this, is there a different approach out there?

var sample_data = [0, 1, 100, 99, 0, 10, 90, 30, 55, 33, 55, 75, 50, 51, 49, 50, 51, 49, 51]

function process(data){

    var result = []
    var a;
    var b;

    for (var i=0; i < data.length; i++) {

        a = data[i];

        for (var j=0; j < data.length; j++) {

            b = data[j]

            if ( (parseInt(a) + parseInt(b)) === 100 && result.indexOf(a+","+b) == -1 && result.indexOf(b+","+a ) == -1 ) {
               result.push( a+","+b )
            }

        }    
    }

    for (var i=0; i < result.length; i++) {
        result[i] = result[i].split(',')
    }

    return result
} 

process(sample_data);

Answer 1

Style

It is considered good practice to terminate all statements with a semicolon, even though they are optional.

Follow namingConventions in JavaScript.

The function should have a more descriptive name than process(). It could take the desired sum as a parameter.

Algorithm

Your function, which relies on brute force, is an inefficient \$O(n^2)\$, bordering on \$O(n^3)\$. It's \$O(n^2)\$ because i takes on \$n\$ values, and for each i, j takes on \$n\$ values. The result.indexOf(…) operations could also be \$O(n)\$ in the worst case, so the overall complexity could be as bad as \$O(n^3)\$.

One simple optimization would be to take advantage of symmetry to cut the work in half:

for (var i = 0; i < data.length; i++) {
    a = data[i];
    for (var j = 0; j < i; j++) {
        …
    }
}

Another simplification would be to avoid stringifying and parsing the number pairs:

result.push([a, b]);

One possible smart solution would be to sort the data, and have i increasing from 0, and j decreasing from the end, until they meet in the middle.

function pairsWithSum(sum, data) {
    data = data.slice(0);
    data.sort(function(a, b) { return a - b; });

    var pairs = [];
    var i = 0, j = data.length - 1;
    while (i < j && i < data.length && j >= 0) {
        var a = data[i], b = data[j];

        if (a + b == sum) {
            pairs.push([a, b]);
            while (i < data.length && data[i] == a) { i++; }
            while (j >= 0 && data[j] == b) { j--; }
        } else if (a + b < sum) {
            while (i < data.length && data[i++] == a);
        } else {
            while (j >= 0 && data[j--] == b);
        }
    }
    return pairs;
}

Answer 2

okay, my javascript is not great but this should find all pairs in a single pass.

this assumes all values are between 0 and 100, like in the question.

Here is a working JSFiddle that shows the code in action.

var sample_data = [0, 1, 100, 99, 0, 10, 90, 30, 55, 33, 55, 75, 50, 51,
                      49, 50, 51, 49, 51];

var found = {};
var results = [];
for(var i of sample_data) {
    if (found[100 - i] === true) {
        // pair found
        results.push({
            a: i,
            b: 100 - i
        });
    }

    found[i] = true;
}

essentially, found is used as a hashset to see if the required reciprocal has already occurred in the array.

This makes the code more concise while being as easy to understand, therefore more maintainable. The code is also likely to have superior performance to code with nested loops.

Answer 3

Nitpicks

function process(data){

On an interview question, I'd prefer to see an answer like

function find_pairs_that_sum_to(numbers, sum) {

That way I can see that you write readable, reusable code.

var result = []
var a;

I find code like this confusing. Why no ; on the first line? Why on the second line? I'd prefer to see consistency in the formatting. Also, I'd name result pairs.

        if ( (parseInt(a) + parseInt(b)) === 100 && result.indexOf(a+","+b) == -1 && result.indexOf(b+","+a ) == -1 ) {
           result.push( a+","+b )
        }

Considering that indexOf is \$O(n)\$, you might want to avoid doing it twice.

        b = parseInt(data[j]);
        if ( (a + b) === sum ) {
          if ( a <= b ) {
            if ( -1 == pairs.indexOf(a+","+b) ) {
              pairs.push( a+","+b );
            }
          } else {
            if ( -1 == pairs.indexOf(b+","+a) ) {
              pairs.push( b+","+a );
            }
          }

          // we don't need to try any more once we have a match
          // move to the next outer loop value
          break;
        }

Note that your algorithm is \$O(n^3)\$. One \$n\$ for each loop and a third for the indexOf. You can argue \$O(n^2m)\$ where \$m\$ is the size of the solution, but the bad case is where the solution is half as large as the input.

Alternative

One of the other answers mentioned using a map, and that will work. However, for working with numbers, an array may do fine. Of course, this stops working if the problem space becomes big. It works fine for a hundred values though.

function find_pairs_that_sum_to(numbers, sum) {
  var is_in_numbers = [];

  for ( var i = 0; i < sum; ++i ) {
    is_in_numbers.push(false);
  }

  for ( var i = 0; i < numbers.length; ++i ) {
    // assumes that all values in numbers are in [0, sum]
    // if that can be untrue, bad values should be caught here

    is_in_numbers[parseInt(numbers[i])] = true;
  }

  var pairs = [];
  var n = sum / 2;
  for ( var i = 0; i <= n; ++i ) {
    if ( is_in_numbers[i] && is_in_numbers[sum - i] ) {
      pairs.push([i, sum - i]);
    }
  }
}

Testing on your sample data produces almost the same result, only the order differs. This function is linear against the solution space (i.e. 101 in this case) or the number of inputs, whichever is larger. You could write that as \$O(m + n)\$

If the solution space is much larger than the number of inputs, then you can change is_in_numbers from an array to a map. That would give you a straight \$O(n)\$ solution.

Answer 4

Firstly, given this is an interview question, an important aspect is to be asking questions. It's very common in the real world to be given a vague spec or a problem that has not been fully considered. If you don't ask, ensure that your program can handle such edge-cases. Be defensive with your code and try to have a bulletproof spec.

Secondly, tests. A great way to blow an interviewer over is to write your tests first, or at least suggest that you would before you start coding. Thinking about tests can help cover the questions that you should be asking anyway and edge-cases you may not have originally thought of, although for the sake of brevity during an interview, they may end up just being a talking point.

As for the problem in question, for the given data set, a naive approach is not going to struggle on a modern computer and if it is genuinely faster for you to code, you could argue that is the fastest solution on that basis. There are some traps to avoid, depending on your approach; a big one depends on interpretation of the problem statement 'return... each pair of integers that add up to 100'. It's not clear if that means that if 0 occurs three times and 100 occurs five times, we should see three pairs of [0, 100] or just a single unique pair. Including all pairs is a more interesting challenge, so I'll assume that from now on until I say otherwise.

The fastest and most scalable algorithm is to build a histogram, that is, to count the number of occurrences of the values (a map or an array can be suitable here). In javascript, using an array, that might look something like this:

var histogram = [101];

for(var i=0; i<histogram.length; i++) { // init
    histogram[i] = 0;
}

for(var i=0; i<data.length; i++) { // populate
    histogram[data[i]]++;
}

Once you have a histogram, we can observe that number pairs that add up to 100 mirror either side of 50 and, as a result, 50 is a special case. For non-50 numbers, we have as many pairs as the smaller frequency of occurrence. Put into code:

var result = [];

for(var i=0; i<floor(histogram[50]/2); i++) {
    result.push([50, 50]);
}

for(var number=0; number<50; number++) {
    var inverse = 100 - number;
    var pair = [number, inverse];
    var numberFrequency = histogram[number];
    var inverseFrequency = histogram[inverse];
    var pairCount = numberFrequency < inverseFrequency ? numberFrequency : inverseFrequency;

    for(var i=0; i<pairCount; i++) {
        result.push(pair);
    }
}

Obviously this approach needs some adjustment if negative numbers are allowed and would probably want to use a map instead to avoid having a potentially sparse and large array. Overall, it only takes O(n) to insert into the histogram and the other aspects are constant, making this approach optimal.

If we do want to do unique pairs, as per your implementation and the alternative interpretation of the problem statement, we can just change the print loops to if statements. However, there is also an extra end condition: if you have encountered all possible pairs, we no longer need to continue building the histogram and can just print all possible pairs and finish. We can adjust the histogram population code to catch this:

// snip: histogram creation and initialisation

var encountered = -1;

for(var i=0; i<data.length; i++) { // populate
    histogram[data[i]]++;

    if(data[i] == encountered + 1) {
        while(histogram[encountered + 1] > 0) {
            encountered++;
        }
        if(encountered == 100) {
            for(var i=0; i<51; i++) {
                result.push([i, 100 - i]);
            }
            break; //end early
        }
    }
}

Answer 5

Depending on the size of your sum quantity, in this case 100, you may want to consider making multiple passes. I've thrown together a quick piece of code that passes my basic tests, although clearly you'd want to perform your own tests!

var pairsWithSum = function(sum, data) {

    // make an array to see how many counts we have
    var counts = new Array(sum + 1);

    // count the number of times each element comes up
    for(var i = 0; i < data.length; i++) {
        if(!counts[data[i]]) {
            counts[data[i]] = 1
        }
        else {
            counts[data[i]]++;
        }
    }

    var pairs = [];
    // walk up from the start of the counts, and
    // match that number with the its "sum - i" pair
    // since that's the only number that will reach the sum
    for(var i = 0; i <= sum / 2; i++) {
        var first = i;
        var last = sum - i;

        // we may have duplicates, for example `pairsWithSum(10, [2,2,8,8]);
        // will have two entries in this code
        while(counts[first] > 0 && counts[last] > 0) {
            pairs.push([first, last]);
            counts[first]--;
            counts[last]--;
        }
    }

    return pairs;
}

This is not without its downfalls, though. Consider something like pairsWithSum(100000000,[1,2,3]) - do we really want to allocate an array of 1000000000 to find pairs in 3 numbers? No, not really. In that case, we'd probably want the logarithmic solution.

I personally would have both implementations, and use a threshold to determine which one is which, programatically determining the threshold based on your target environment and resource constraints. A quick rule of thumb I would use is if n * lg(n) < sum then you would want to use the logarithmic version. Otherwise, use the memory-hog we have here. But which you use in production depends heavily on your resource constraints.

Answer 6

I do not know how to code in JavaScript, but here are a few algorithms you can use:

• Take a integer and run through the loop to find 100-arr[i]. (The one you used) Time complexity: \$O(n^2)\$

• Sort the array (\$O(nlogn)\$) and traverse the array from both the ends to get the pairs

  Say a sorted array is: {1,3,50,50,97}.

  • Traverse the array with startIndex = 0 and endIndex = array's size-1
  • Run the loop to see if arr[startIndex]+arr[endIndex]=N (100)
  • If = record and increment startIndex and decrement endIndex
  • If < increment startIndex
  • else (If >) decrement endIndex.

• Have a map with key as the arr[i] and key as its count. Time complexity \$O(n)\$ and space complexity \$O(n)\$.

  • Check if N-arr[i] is present in the Map.
  • If not, put the arr[i] into the map and increment its value.
  • If yes, you have a pair. Enjoy. Remember to decrement N-arr[i]

Answer 7

I present an algorithms in pseudocode. Actually I don't use some pseudocode grammar invented by me but I use Python and avoid Python specific idioms. I think this is readable even if one has no knowledge of Python at all but nevertheless it has a precise meaning and can be executed and tested (e.g. here).

---

The following algorithm will do it in \$O(n \log(n)\$ time and $O(n)$ space. \$O(n \log(n)\$ time is needed for sorting the array. Scanning the sorted array and finding the solutions takes \$O(n)\$ time, because each list element is accessed at most once. Your algorithm will take \$O(n^2)\$ time, because you execute two nested for loop, each of them stepping through the number list of length \$n\$.

number=[0, 1, 100, 99, 0, 10, 90, 30, 55, 33, 55, 75, 50, 51, 49, 50, 51, 49, 51]
target=100
number.sort()
i=0
j=len(number)-1
lo=number[i]
hi=number[j]
while (True):
    sum=lo+hi
    if sum > target:
        j=j-1
        if j<=i:
            break
        hi=number[j]
    elif sum<target:
        i=i+1
        if i>=j:
            break
        lo=number[i]
    else:
        print(lo,hi)
        j=j-1
        i=i+1
        if ((i>=j)):
            break
        lo=number[i]
        hi=number[j]