Changing O(n^3) to O(n^2) in JavaScript [duplicate]

Question

I'm trying to wrap my head around saving time in my coding solution.

I have a function called tripletSum which takes two parameters x and a where x is a number and a is an array.

This function is supposed to return true if the list a contains three elements which add up to the number x, otherwise it should return false.

I've created the following working solution:

function tripletSum(x, a) {
    for(var i = 0; i < a.length; i++) {
        for(var j = i + 1; j < a.length; j++) {
            for(var k = j + 1; k < a.length; k++) {
                if((a[i] + a[j] + a[k]) === x) {
                    return true;
                }
            }
        }
    }
    return false;
}

But this doesn't seem like the best practice. Currently the time it takes to run through this function is O(n^3) if I'm not mistaken and I think it can be improved to have a time complexity of O(n^2).

Anyway I can change this code to do that?

Edit: This is not a duplicate of the other question because I was asking for a specific improvement on my current example in JavaScript which is not what it asked in the marked duplicate question.

Answer 1

Keep a dictionary-like object for all the keys contained in the array. Then in your second loop you subtract the two values from x and look for that value in your dictionary.

function tripletSum(x, a) {
    var dictionary = {};
    for(var i = 0; i < a.length; i++) {
        dictionary[a[i]] = true;
    }

    for(var i = 0; i < a.length; i++) {
        for(var j = i + 1; j < a.length; j++) {
            var remainder = x - a[i] - a[j];
            if(dictionary[remainder])
                return true;
        }
    }
    return false;
}

Answer 2

Here is the idea: you need firstly to sort the array a. After that you can have one loop which iterates through all elements from 0 up to N - 2 (exclusively). Let's call i the index of this loop. Here comes the usefulness of the fact that the array is sorted. We we'll use the knowledge that the array is sorted to "squeeze" the "unprocessed" subarray (range from i + 1 to N-th element). You will now have 2 values left and right. left will indicate the left index of the unprocessed subarray, while right will indicate the right index of that unprocessed part of the array. At the beginning we set left = i + 1 and right = N - 1. We calculate the sum a[i] + a[left] + a[right]. Now we have 3 cases:

1. If sum = x then return true
2. If sum > x then we need to make the sum lower, so we need to decrement right by 1 (squeeze from right)
3. If sum < x then we need to make the sum greater, so we need to increment left by 1 (squeeze from left)

Here follows the Javascript solution.

function tripletSum(x, a) {
    a.sort(function(i, j) {
        return i - j;
    });

    var N = a.length;

    for(var i = 0; i < N - 2; i++) {
        var left = i + 1, right = N - 1;

        while(left < right) {
            var sum = a[i] + a[left] + a[right];
            if(sum === x) {
                return true;
            }
            else if(sum > x) {
                right--;
            }
            else {
                left++;
            }
        }

    }

    return false;
}

The time complexity is O(N^2) and no additional space is being used.