Changing O(n^3) to O(n^2) in JavaScript

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.

http://codereview.stackexchange.com might get you a better answer — Jamiec, Jun 12 '17 at 21:15
Start by sorting - http://www.geeksforgeeks.org/find-a-triplet-that-sum-to-a-given-value/ — Ori Drori, Jun 12 '17 at 21:16

score 6 · Answer 1 · answered Jun 12 '17 at 21:16

6

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;
}

answered Jun 12 '17 at 21:16

Frederik Hansen

506
4
21

I ran a test case with this solution using `x = 5`, `a = [2, 3, 1]` and it returned `false`. – Barry Michael Doyle Jun 12 '17 at 21:26
1

That would be the expected behaviour? The only triplet in that array adds up to 6. – Alex Young Jun 12 '17 at 21:56
RIght sorry blond moment... – Barry Michael Doyle Jun 13 '17 at 07:10

giliev · Accepted Answer · 2017-06-13T09:13:10.397

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:

If sum = x then return true
If sum > x then we need to make the sum lower, so we need to decrement right by 1 (squeeze from right)
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.

Piyush · Answer 3 · 2017-06-12T23:52:57.913

You can basically make use of binary search and a sort to reduce the complexity to O(n^2*logn) from O(n^3).

function tripletSum(x, a) {
    a.sort(function(a, b) {
            return a - b
        }) // O(n*logn)
    var n = a.length;
    for (var i = 0; i < n; i++) {
        for (var j = i + 1; j < n; j++) {
            if (a.indexOf(x - a[i] - a[j]) > j) {
                return true; //O(n^2*logn)
            }
        }
    }
    return false;
}

console.log(tripletSum(0, [
    1,
    5,
    6,
    -2, 
    -3
]))

Total complexity = O(n*logn) + O(n^2*logn) ~ O(n^2*logn)

Changing O(n^3) to O(n^2) in JavaScript

3 Answers3