LeetCode Problem

Problem Description

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.

Examples

Input: [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Input: [0,1,1]
Output: []

Constraints

0 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

Follow-up

Approach to Solve

Sort the array and use a two-pointer technique to find triplets that sum to zero.

Code Implementation

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left, right = i + 1, len(nums) - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total < 0:
                    left += 1
                elif total > 0:
                    right -= 1
                else:
                    result.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
        return result

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                }
            }
        }
        return result;
    }

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;
        for (int i = 0; i < nums.size() - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = nums.size() - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                    result.push_back({nums[i], nums[left], nums[right]});
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                }
            }
        }
        return result;
    }
};

Explanation

The 3Sum problem is solved using a combination of sorting and two-pointer technique. Here's a detailed explanation of the approach:

Sort the input array: This is crucial for the two-pointer technique to work efficiently.
Iterate through the array: For each element nums[i], we'll find two other elements that sum up to -nums[i].
- We only need to iterate up to the third-to-last element, as we need at least two more elements after i.
Skip duplicates: If the current element is the same as the previous one, skip it to avoid duplicate triplets.
Two-pointer technique: For each i, initialize two pointers:
- left: points to the element right after i
- right: points to the last element of the array
While left < right:
- Calculate the sum of nums[i] + nums[left] + nums[right]
- If sum < 0, increment left (we need a larger sum)
- If sum > 0, decrement right (we need a smaller sum)
- If sum == 0, we've found a valid triplet:
  - Add it to the result
  - Skip duplicates for both left and right pointers
  - Move both left and right pointers inward
Time Complexity: O(n^2)
- Sorting takes O(n log n)
- The nested loops (one explicit, one implicit in the while loop) take O(n^2)
- Overall, O(n log n + n^2) = O(n^2)
Space Complexity: O(1) or O(n)
- O(1) if we don't count the space for the output
- O(n) if we count the space for the output (in the worst case, there could be O(n^2) triplets)

This approach efficiently handles duplicate triplets and minimizes unnecessary comparisons by skipping duplicates and using the sorted nature of the array.

Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)