15. 3Sum

Problem Description

This problem asks us to find all the unique triplets in an array that can combine to give a sum of zero. A triplet in this context is defined as a set of three numbers [nums[i], nums[j], nums[k]] where each number comes from a different position in the array, indicated by i, j, and k. Importantly, we need to ensure that:

1. The indices i, j, and k are all different.
2. The sum of the numbers at those indices is zero (nums[i] + nums[j] + nums[k] == 0).
3. No triplet is repeated in the result.

Our goal is to identify all such combinations, ensuring that each combination of three numbers is unique within the result set. This problem is a classic example of a challenge involving array manipulation and the identification of specific patterns within a numerical set.

Intuition

To arrive at the solution for this problem, we will follow a two-step approach. First, we sort the array in non-decreasing order. The sorting helps us in two ways: it makes it easy to avoid adding duplicate triplets and allows us to use the two-pointer technique effectively.

After sorting, the array is processed with a loop that effectively tries out each number as a potential candidate for the first number of the triplet. This candidate is referred to as nums[i]. Starting from i = 0, we will check whether nums[i], when added to any two other numbers in the array to its right, sums to zero.

To expedite the process and avoid checking combinations that are guaranteed to fail or are redundant, we make use of the following insights:

1. If the current number nums[i] is greater than zero, because the array is sorted, any combination involving this and subsequent numbers will be greater than zero. Since no sum with a positive total can equal zero, we can break out of the loop early.

2. If nums[i] is the same as the previous number nums[i-1], we skip the current value to prevent processing the same triplet scenario, which would lead to duplicates.

Once a valid nums[i] is chosen, we employ a while loop using two pointers, j and k, that start after i (for j) and at the end of the array (for k). We calculate the sum of nums[i], nums[j], and nums[k]. If the sum is:

• Less than zero, we move j to the right to increase the sum (nums[j] will be larger).
• Greater than zero, we shift k to the left to decrease the sum (because nums[k] will get smaller).
• Exactly zero, we have found a valid triplet and add it to our solution set. We then move both j and k pointers, skipping over any duplicates to look for additional triplets starting with nums[i].

We repeat this process for every index i until the second last element, and collect all unique triplets that give us a sum of zero.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The code implements a sort and two-pointer strategy to find all unique triplets summing to zero in the nums array. Below are the detailed steps taken by the implementation, following the Reference Solution Approach:

1. Sort the Array: First, we sort the array using nums.sort(). Sorting is beneficial as it orders the elements, allowing us to employ the two-pointer method effectively, and it makes it easier to avoid duplicates since duplicate values will be adjacent in a sorted array.

2. Iterate Over Possible First Elements of Triplets: We look at each number in the nums array (up until the third-to-last element) to be the potential first element of our triplet. This is achieved with a for loop: for i in range(n - 2).

3. Early Breaks and Continues: Inside this loop, we have some conditions that help us eliminate unnecessary checks:

   • If the current number nums[i] is greater than zero, we can break out of the loop. This is because any triplet involving a positive starting number will have a sum greater than zero.
   • If the current number is the same as the previous number (and i is not 0), we use continue to skip to the next iteration to avoid checking for duplicates.

4. Two-Pointer Technique: For each i, we use two pointers, j and k, initialized to i + 1 and n - 1 (the end of the array), respectively. We then enter a while loop, which will continue as long as j is less than k.

5. Find the Triplets: Within the while loop, we calculate the sum x of nums[i], nums[j], and nums[k] and compare it to zero:

   • If x is less than zero, we increment j since we need a larger number to increase the sum.
   • If x is greater than zero, we decrement k as we need a smaller number to decrease the sum.
   • If x is zero, we have found a valid triplet and we add [nums[i], nums[j], nums[k]] to ans. After storing the triplet, we move both j and k past any duplicates to ensure we don't find duplicates in subsequent iterations.

6. Return the Result: Once all numbers have been considered for the first element of the triplet, and all valid j, k pairs have been evaluated, we return ans. This list contains all the unique triplets that add up to zero.

This solution has a time complexity of O(n^2) and a space complexity of O(log n) due to the sort operation, assuming that the sort() method used takes O(log n) space for the internal stack during a sorting algorithm like quicksort or mergesort. However, if the sorting does not take extra space, then the space complexity will only be O(1), which is the space taken by the output array and the pointers used.

Example Walkthrough

Let's walk through the solution approach using a small example. Consider the array nums = [-1, 0, 1, 2, -1, -4].

Following the steps in the solution approach:

1. Sort the Array: We start by sorting nums, resulting in [-4, -1, -1, 0, 1, 2].

2. Iterate Over Possible First Elements of Triplets: We start looking through the array for potential first elements of the triplet. The loop runs from the start of the array to n - 3, where n is the length of the sorted nums array.

3. Early Breaks and Continues: As we loop through, if we find a number larger than zero (nums[i] > 0), we can break out of the loop. In our example, all numbers from the index 0 to n - 3 will be considered since the break condition does not become true.

We also skip the second element, which is -1, same as the first, using continue to avoid duplicates.

4. Two-Pointer Technique: We start the two-pointer process with i, j, and k as follows:

   • i = 0: We choose -4 as the first element.
   • j = i + 1: j starts at -1 (the element right after -4).
   • k = n - 1: k starts at 2 (the last element).

5. Find the Triplets: In the while loop, we find sums of nums[i] + nums[j] + nums[k] and adjust j and k accordingly:

   • The first sum is -4 + -1 + 2 = -3, which is less than zero. We increment j to move to the next larger number, which is another -1.
   • Now, the sum is -4 + -1 + 2 = -3, still less than zero. We increment j again and move to 0.
   • With j on 0, the sum is -4 + 0 + 2 = -2, and we continue incrementing j to move to 1.
   • The sum is now -4 + 1 + 2 = -1, which is still less than zero, so we move j again, but now we've reached the end, and the while loop ends for this i.

Next, with i = 1, we find:

• i = 1 (but this is skipped because it's the same as i = 0).
• i = 2, we have the first element as -1, j = 3 and k = 5, so we test the combination -1 + 0 + 2, which sums to 1. The sum is greater than zero, so we decrement k.
• Now, k is 4, and j is 3, so we test -1 + 0 + 1, which sums to 0. We've found a valid triplet [-1, 0, 1].

Each time we find a triplet, we move both j and k while they point to the same number to avoid duplicates. In this case, there are no duplicates, and we are done with this iteration.

6. Return the Result: After evaluating all potential starting points, the solution returns the list of unique triplets found. In this case, [[-1, 0, 1]] is the only unique triplet that sums to zero.

The implementation would return [[−1, 0, 1]] as the output.

Following the outlined process, we can find all possible unique triplets in the array that can combine to give a sum of zero.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n^2). This is because there is a nested loop where the outer loop runs for n times (reduced by 2 to avoid unnecessary last iterations due to triplets), and within this loop, there are two pointers that are moving independently towards each other, which in total will lead to n iterations in the worst case. There are no nested loops inside the while loop, so the inner operations are constant time notwithstanding the while conditions which are also O(n). Multiplying these together gives us n * n = n^2, hence O(n^2).

Space Complexity

The space complexity of the code is O(log n) if we don't take the output space into consideration, which would be O(n). The space complexity arises due to the space used by the sorting algorithm, which is typically O(log n) for the commonly used algorithms like QuickSort or MergeSort in many standard programming libraries.

Learn more about how to find time and space complexity quickly using problem constraints.