Problem Informations

Problem Index: 15
Problem Link: 3Sum
Topics: Array, Two Pointers, Sorting

Problem Description

Given an integer array nums, return all the triplets $[nums[i], nums[j], nums[k]]$ such that $i \neq j$, $i \neq k$, and $j \neq k$, and $nums[i] + nums[j] + nums[k] = 0$.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
$nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0$.
$nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0$.
$nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0$.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

Constraints:

$3 \leq nums.length \leq 3000$
$-10^5 \leq nums[i] \leq 10^5$

Intuition

The problem requires finding all unique triplets in the array which sum up to zero. A straightforward approach is to use a brute-force method by checking each combination of triplets in the array. However, this would be computationally expensive with a time complexity of $O(n^3)$. Instead, sorting the array and using a two-pointer technique allows for a more efficient solution, which can reduce the complexity to $O(n^2)$. Sorting helps in identifying potential combinations and facilitates avoiding duplicates efficiently.

Approach

Sorting the Array: Begin by sorting the input array nums. Sorting is crucial as it allows us to employ the two-pointer technique more effectively. The order of elements doesn’t matter when considering their sum, but sorting helps in easily managing and skipping duplicates.
Iterate Through the Array: Loop through each element in the array up to the third last element, since we need at least three elements to form a triplet.
Two-Pointer Technique: For each element at index i, set two pointers — left initialized to i + 1 and right initialized to the last index of the array. These pointers will help find two additional numbers whose sum with nums[i] is zero.
Sum Calculation and Adjustment:
- Calculate the sum of the triplet nums[i] + nums[left] + nums[right].
- If the sum is greater than zero, decrement the right pointer to reduce the sum.
- If the sum is less than zero, increment the left pointer to increase the sum.
- If the sum equals zero, a valid triplet is found. Add this triplet to the result set and adjust both left and right pointers to continue searching for other possible triplets. Ensure to skip over duplicate values to maintain the uniqueness of triplets by avoiding duplicate elements.
Avoiding Duplicates:
- After processing a potential triplet, move the left and right pointers past any duplicate numbers by ensuring the newly positioned left and right point to elements that are different from the previous left and right respectively.
- Additionally, skip any duplicate starting elements nums[i] to prevent forming identical triplets multiple times.
Return Result: After all possible triplets are checked, return the result list containing all the unique triplets that sum to zero.

This method leverages sorting and the two-pointer technique to efficiently explore possible combinations and maintain the uniqueness of results by avoiding duplicates, providing an optimal solution with a time complexity of $O(n^2)$.

Code

C++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // Vector to store the resulting triplets
        vector<vector<int>> result;
        
        // Sort the array to facilitate the two-pointer approach
        sort(nums.begin(), nums.end());

        // Traverse each element in the array
        for (int i = 0; i < static_cast<int>(nums.size()) - 2; i++) {
            int left = i + 1;  // Initialize left pointer
            int right = nums.size() - 1;  // Initialize right pointer
            
            // While there is a possibility to form a triplet
            while (left < right) {
                // Calculate the sum of the triplet
                int sum = nums[i] + nums[left] + nums[right];
                
                if (sum > 0) {
                    // Decrement right pointer if sum is greater than zero
                    do {
                        right--;
                    } while (left < right && nums[right] == nums[right + 1]);  // Avoid duplicate elements
                } else if (sum < 0) {
                    // Increment left pointer if sum is less than zero
                    do {
                        left++;
                    } while (left < right && nums[left] == nums[left - 1]);  // Avoid duplicate elements
                } else {
                    // If sum equals zero, add the triplet to result
                    result.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    
                    // Move both pointers and avoid duplicates for both ends
                    do {
                        left++;
                    } while (left < right && nums[left] == nums[left - 1]);
                    do {
                        right--;
                    } while (left < right && nums[right] == nums[right + 1]);
                }
            }
            // Avoid considering the same value of nums[i] by skipping duplicates
            while (i < static_cast<int>(nums.size()) - 2 && nums[i] == nums[i + 1]) i++;
        }
        
        return result;
    }
};

Python

class Solution:
    def threeSum(self, nums):
        # List to store the resulting triplets
        result = []
        
        # Sort the list to facilitate the two-pointer approach
        nums.sort()

        # Traverse each element in the list
        for i in range(len(nums) - 2):
            left = i + 1  # Initialize left pointer
            right = len(nums) - 1  # Initialize right pointer
            
            # While there is a possibility to form a triplet
            while left < right:
                # Calculate the sum of the triplet
                sum_ = nums[i] + nums[left] + nums[right]
                
                if sum_ > 0:
                    # Decrement right pointer if sum is greater than zero
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1  # Avoid duplicate elements
                    right -= 1
                elif sum_ < 0:
                    # Increment left pointer if sum is less than zero
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1  # Avoid duplicate elements
                    left += 1
                else:
                    # If sum equals zero, add the triplet to result
                    result.append([nums[i], nums[left], nums[right]])
                    
                    # Move both pointers and avoid duplicates for both ends
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    right -= 1
            
            # Avoid considering the same value of nums[i] by skipping duplicates
            while i < len(nums) - 2 and nums[i] == nums[i + 1]:
                i += 1
        
        return result

Complexity

Time complexity: $O(n^2)$

The primary components of the time complexity include sorting the array and the nested loops that look for triplets. Sorting the array requires $O(n \log n)$ time, where $n$ is the length of the array. The nested loop structure for finding the triplets is $O(n^2)$ in the worst case, as we iterate through the array with two pointers for each element. Consequently, the overall time complexity is $O(n \log n + n^2)$. Given $n^2$ dominates $n \log n$ for large $n$, the time complexity is simplified to $O(n^2)$.

Space complexity: $O(n)$

The space complexity is primarily due to the storage required for the output, which, in the worst-case scenario, can store up to $O(n)$ triplets. The space used for sorting is $O(1)$ if using in-place algorithms or $O(n)$ if not, but this is typically considered negligible compared to the space used for storing results. Thus, the overall space complexity is $O(n)$.

CS Note
中

Leetcode 15. 3Sum