After TwoSum there's ThreeSum  Solving Leetcode Challenge in JavaScript
Solving the ThreeSum Problem with JavaScript
A great and classic challenge, 3Sum and extremely popular for interviews. It can be solved with variying level of efficiency and beauty. Its a simple problem on the face of it, but there are a couple things that make it tricky. Evidence how much 3Sum is loved:

This Quora thread

More than 1.5 million submissions, 320k Accepted answers and 1500+ upvotes on leetcode.
Among some of the unresolved problems in Computer Science on planet earth, there remains this one  Can 3SUM be solved in O(n^{1.99999}) time i.e. better than O(n^2) time ?
It’s conjectured to be impossible to find an O(n^(2−ϵ))
algorithm for solving 3SUM, for any positive constant ϵ. Although, a pretty recent research, shaved off some log factors for the 3SUM problem giving a subquadratic deterministic algorithm : Threesomes, Degenerates, and Love Triangles and probably the best known general algo for 3Sum at the moment.
The Problem Statement  Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate triplets. Example: Given array nums = [1, 0, 1, 2, 1, 4]
A solution set is: [ [1, 0, 1], [1, 1, 2] ]
Solution1Brute Force
The requirement is to find all unique triplets in the array. That is, the solution set must not contain duplicate triplets. This means in the resultant array, no number would be repeated. So, I wil achieve this with the following technique.
A> The most simple way to remove duplicates is to stop considering the same value for the same index more than once. Don’t let i, j or k refer to the same value in the array twice. Let x refer to some value in the array. Once we have set i=x and found all y, z such that x+y+z=0, we never have to consider setting i=x again.
B> First sort the array. So if there are multiple numbers, like two 5’s they will come sequentially. So, whilte iterating for say i
, I will hit the two sequential 5's
in my two sequential iteration. So I can skip over the second iteration, usingn continue
.
C> So after sorting the array, will check for each iteration that the current element that I am taking is not === previous element. That is if nums[i] === nums[i1]) continue
D> An example below of stopping duplicates..
My First native brute force solution below of traversing the array 3 times checking for all combinations of 3 numbers if their sum produces zero. Although the code produced the correct result in my local machine, but it took so long in Leetcode’s exhaustive testcases, that it gave me “TIME LIMIT EXCEEDED” error there in Leetcode.
See the Pen 3sumbrute force blog by Rohan Paul (@rohanpaul) on CodePen.
Note, the 2nd and 3rd for loops (indexed by j and k) stars from i+1
and j+1
respectively, skipping over indices that are already used, instead of 0. This is so, because, suppose we found a triplet, a0, a1, a2
with j pointing to a0
and i pointing to a1
with j < i
. Then, we would have found the same triplet with i
pointing to a0
and j
pointing to a1
on a previous iteration giving us a duplicate output.
Complexity Analysis
Time complexity : O(n^3)
Because each of these nested loops executes n times, the total time complexity is O(n^3), where n is a size of an array.
Space complexity : O(n^2). If we assume that resultant array is not considered as additional space we need O(n^2) space for storing triplets in a set.
Solution2 First iteration at finding a "2pointersolution"
that runs in O(n^2)
Time
See the Pen 3Sum2PointerSolution2ndBestBlog by Rohan Paul (@rohanpaul) on CodePen.
This runs hugely faster vs the Brute Force one, however, there’s still little room for optimization to the above code. If I put the a line if (arr[aIndex] > 0) return result
immediately after I start the first for loop (i.e immediately inside for (let indexA = 0; indexA < arr.length  2; indexA++)
) in the above code, it will gain some performance, because I will be skipping many iterations as soon as I hit the first elementvalue of the required resultarray to be more than zero. So, below is my little more optimized version of a 2pointer solution.
Solution3 Even Faster than above after little optimization "2pointersolution"
in O(n^2)
Time
The Algo
A> As a first step, just like the previous solution, since we’re dealing with an array of numbers it makes great sense to sort things before diving into algorithm mechanics.
B> Instead of 3 nested for loops, here I will use 1 forloop and one whileloop. Fix the first element as array[i] where i is from 0 to array size – 2. After fixing the first element of triplet, find the other two elements using a while
loop.
C> I will invoke the forloop for (let indexA = 0; indexA < nums.length  2; indexA++)
and the first statement in my forloop will allow the first iteration to run and skip over any subsequent iterations that would lead to the same calulation. So, if my array becomes [1,1,1,3,3] and I am looking at the 0 element 1  I no more iterate any further.
D> Now with each iteration of the first for loop, keeping a's
value constant, I am looping the values of the next 2 variables b
and c
to check if (a + b + c = 0)
. b
starting from indexA + 1 and increasing and c
starting from the end of the array nums.length  1
and decreasing.
Since the number array is sorted, the plan is to pull b and c closer together  checking each time for the sum array values to equal 0.
E> If I see that the result (sum of Triplets i.e a + b + c) is more than zero, I can decrement from rightmost elements to reach zero.
And if the result is less than zero, I increment the b’s (middle element in the triplet) value to reach zero. Pictorially..
F> After all values of b
and c
are exhausted, I go back to the next iteration of the for loop for the next value of a
.
Given a
has the lowest value after sorting the array, and with each value of a
, I have already iterated through checking for all values of b
and c
to check if sum is zero  as soon as a
becomes > 0 I can return from the function. Because it means I have reached a point where all the subsequent values of the array will be higher than zero. So no point in iterating further when a > 0
.
G> And a
will only take values upto (nums.length  3)
as the last 2 values will be taken by the subsequent 2 variables b
and c
See the Pen 3sumSolution2HashMapBlog by Rohan Paul (@rohanpaul) on CodePen.
And see the huge performance difference with the 3 approaches to soution, running the code for an array with 2000 randomly generated elements.
var arr = Array.from({length: 2000}, () => Math.floor(Math.random() * 3000));
console.time("Solution1Brute Force");
threeSum_Brute(arr);
console.timeEnd("Solution1Brute Force");
console.log("***************************************************");
console.time("Solution2SubObtimal2Pointer");
threeSum2 (arr);
console.timeEnd("Solution2SubObtimal2Pointer");
console.log("***************************************************");
console.time("Solution3OptimizedTwoPointer");
threeSumTwoPointer(arr);
console.timeEnd("Solution3OptimizedTwoPointer");
And output of the above the test above
Solution1Brute Force: 2772.645ms
***************************************************
Solution2SubObtimal2Pointer: 8.542ms
***************************************************
Solution3OptimizedTwoPointer: 1.221ms