15. 3Sum
Problem
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Example 2:
Example 3:
Constraints:
- 3 <= nums.length <= 3000
- -105 <= nums[i] <= 105
Approach
To solve this, we can use a similar approach to Two Sum II - Input Array Sorted.
The idea is that for each number, we want to run the algorithm for Two Sum II on the remaining elements using the current number's negation as the target. However, this will require sorting the input array to start. We don't need to worry about the elements before the current number because the problem states to return the distinct triplets.
Let's go through an example with Example 1:
We have the input array: [-1, 0, 1, 2, -1, 4]. After sorting, we have: [-1, -1, 0, 1, 2, 4].
Now, for the first iteration, we're treating, arr[0] = -1 as our current number (target = 1) and we'll run the two-pointer algorithm on the remaining elements: [-1, 0, 1, 2, 4]. In other words, we're looking in that subset for two numbers that add up to 1 because then the triplet will add up to 0. We can set up our two pointers and increment/decrement based upon whether the current target is less than or greater than the target. We'll find that -1, 2 add up to 1 (target) so we can add that triplet to our list. We'll continue this way until we finish the iteration. See Two Sum II - Input Array Sorted for details on the algorithm we're running on the subset.
Another important note is in regards to duplicate triplets. We can mitigate this by skipping over numbers we've already processed. Since the array is sorted, all duplicates will be beside eachother. Therefore, in the main loop, we can check if the next number is the same as the current and skip the current. In the inner loop, when we find a triplet, we can keep incrementing/decrementing until we are at the last occurrence of the particular number before moving on to finding any more triplets with that target.
Complexity
Time: O(n^2)
Sorting the input array is n log n. After that we iterate over the array twice, which is O(n^2). Adding them together, we get O(n log n) + O(n^2) = O(n^2) (we drop lower order terms).
Space: O(1)
No extra space is created.