Solving The Three Number Sum (Code Challenge)
In one of my previous posts, I went over the two number sum problem. We were able to solve the problem with two different methods, the brute force way (nested for loops) and two pointers. First we went through the problem using the brute force method. We setup a nested for loop to iterate through the array and add up each pair of sums. This method results in O(n²) time complexity. Then we used the the two pointer method. We set up a left pointer at first index of the array and right pointer at last index of the array (hence the name two pointers). We added the initial indices and see if we get the result. If the outcome is lower than requested sum, we move the left pointer right. And if the outcome is higher, then we move the right pointer left.
Now that we have a general review of the two sum problem, lets take a look at the three sum problem and see how we can take on this question with a similar method.
Like the two number sum question, we can use the brute force method and use two nested for loops to get the answer. However with the brute force method, the time complexity would be O(n³) and it is not acceptable. So how do we implement the two pointer method in this case?
First, if we are going to follow the similar logic of moving the pointers depending if the sum is larger or smaller, then we will need to have a sorted array. Since I am using Javascript, I call the built in method .sort to arrange the array from low to high. Running sort in Javascript will automatically bring out time complexity to O(n log(n)) time.
With a sorted array, we can now iterated through the array. First we set our initial index at zero. Then we set the left pointer at one index right of our first index and our right pointer at the last index of the array. In our given example, the left pointer would be at -6, and right point would be at 12.
Our goal in this example is to find the three indices (if any) that sum up to zero. Just like the two number sum question, we can now move the left pointer right if the number is too small, or the right pointer left if the number is too big. We would run this comparison for ever number in the array, hence making this time complexity O(n²).
In our solution above, we had to made sure our initial index is at least two indices away from the end to be able to use the two pointer method. The total time complexity would be O(n log(n)) (for our sort method) + O(n²). Since the second portion is greater, we would just use O(n²) for the time complexity. As for the space complexity, it would be O(n) since we are putting the indices for each combination that equals to zero.
