7

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.

Improve this question
3

3 Answers 3

Reset to default
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; }
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

I ran a test case with this solution using x = 5, a = [2, 3, 1] and it returned false.
That would be the expected behaviour? The only triplet in that array adds up to 6.
RIght sorry blond moment...
3

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.

Improve this answer

Comments

0

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)

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.