Problem Number: 15 Difficulty: Medium Category: Array, Two Pointers, Sorting LeetCode Link: https://leetcode.com/problems/3sum/
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:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
The triplets [-1,0,1] and [-1,-1,2] sum to zero.
Example 2:
Input: nums = []
Output: []
Example 3:
Input: nums = [0]
Output: []
Constraints:
3 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5
I used a Sorting + Two Pointers approach. The key insight is to sort the array first, then use a fixed first element and two pointers to find the remaining two elements that sum to the negative of the first element.
Algorithm:
- Sort the array to enable two-pointer technique
- Iterate through each element as the first element of the triplet
- Skip duplicates for the first element to avoid duplicate triplets
- Use two pointers (left and right) to find the remaining two elements
- Skip duplicates for the second and third elements
- Add valid triplets to the result
The solution uses sorting and two-pointer technique to find all unique triplets. See the implementation in the solution file.
Key Points:
- Sorts the array to enable efficient two-pointer search
- Uses three nested loops: outer loop for first element, two pointers for remaining elements
- Skips duplicates at all three levels to avoid duplicate triplets
- Handles edge cases like empty array or insufficient elements
Time Complexity: O(n²)
- Sorting: O(n log n)
- Two-pointer search for each element: O(n²)
- Total: O(n²)
Space Complexity: O(1) (excluding output)
- Uses only a constant amount of extra space
- Output space is O(n²) in worst case for storing all triplets
-
Sorting Enables Two Pointers: Sorting the array allows us to use two pointers efficiently to find pairs that sum to a target.
-
Fixed First Element: By fixing the first element, we reduce the problem to finding two elements that sum to -first_element.
-
Duplicate Handling: We need to skip duplicates at all three levels to avoid duplicate triplets in the result.
-
Two Pointer Optimization: When sum < 0, move left pointer right; when sum > 0, move right pointer left.
-
Early Termination: If the first element is positive, we can stop since all remaining elements will also be positive.
-
Target Calculation: For each first element nums[i], we look for two elements that sum to -nums[i].
-
Brute Force Approach: Initially might consider O(n³) approach checking all possible triplets.
-
Duplicate Handling: Forgetting to skip duplicates at any of the three levels.
-
Wrong Pointer Movement: Moving pointers incorrectly based on the sum comparison.
-
Edge Cases: Not properly handling cases with fewer than 3 elements.
- Two Sum (Problem 1): Finding two elements that sum to target
- Two Sum II - Input Array Is Sorted (Problem 167): Two sum in sorted array
- 4Sum (Problem 18): Extension to finding four elements that sum to target
- 3Sum Closest (Problem 16): Finding triplet with sum closest to target
- Hash Set: Use hash set to store complements - O(n²) time, O(n) space
- Brute Force: Check all possible triplets - O(n³) time complexity
- Binary Search: Use binary search instead of two pointers - O(n² log n) time
- Duplicate Triplets: Not properly handling duplicates in the result set.
- Wrong Complexity: Using brute force approach instead of optimized solution.
- Pointer Movement: Incorrectly moving pointers based on sum comparison.
- Edge Cases: Not handling empty arrays or arrays with fewer than 3 elements.
- Sorting Overhead: Forgetting that sorting is necessary for the two-pointer approach.
|
Note: This is a classic problem that extends the two-sum concept and introduces the importance of handling duplicates in combination problems.