This problem requires iterating through a sorted array and using a two-pointer approach to find all triplets summing to zero while skipping duplicates. Start by fixing one element and then move two pointers inward to meet the target sum. Careful management of duplicate elements is crucial to ensure only distinct triplets are returned, otherwise the solution will include repeated combinations, violating the uniqueness requirement.
Problem Statement
Given an integer array nums, return all distinct triplets [nums[i], nums[j], nums[k]] where i, j, and k are different indices and the sum equals zero. The order of triplets or elements inside triplets does not matter, but duplicates must be avoided. You must find all possible unique combinations efficiently while handling arrays with up to 3000 elements and values ranging from -10^5 to 10^5.
For example, given nums = [-1,0,1,2,-1,-4], the valid triplets are [-1,0,1] and [-1,-1,2]. Arrays with fewer than three elements or no combination summing to zero return an empty list. The problem tests array manipulation, sorting, and two-pointer scanning with invariant tracking to handle sums and skip repeated values effectively.
Examples
Example 1
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
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: []
The only possible triplet does not sum up to 0.
Example 3
Input: nums = [0,0,0]
Output: [[0,0,0]]
The only possible triplet sums up to 0.
Constraints
- 3 <= nums.length <= 3000
- -105 <= nums[i] <= 105
Solution Approach
Sort and Fix One Element
Begin by sorting the array to enable two-pointer scanning. Iterate through each number as a fixed first element, skipping duplicates to maintain unique triplets. Sorting ensures that pointers can move deterministically: left pointer increases and right pointer decreases to reach the target sum, allowing the algorithm to systematically cover all combinations without missing or repeating triplets.
Two-Pointer Scan for Remaining Pair
After fixing the first element, initialize two pointers: one immediately after the fixed element and one at the end of the array. Calculate the sum of the three elements. If the sum is zero, record the triplet and skip any duplicates by advancing the left pointer and decreasing the right pointer. If the sum is less than zero, move the left pointer to increase the sum; if greater than zero, move the right pointer to decrease it. This preserves the invariant that all pairs are checked once.
Handle Duplicates and Collect Results
After each valid triplet is found, continue scanning while skipping over identical elements on both ends to prevent duplicate triplets in the result. Repeat this process for all positions of the fixed element. This approach ensures that each distinct combination is captured exactly once, leveraging the sorted array property and two-pointer invariant tracking. Edge cases, like multiple zeros or repeated negative numbers, are managed naturally by the duplicate skipping logic.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Sorting the array takes O(n log n), and each fixed element triggers a two-pointer scan of O(n), giving an overall time complexity of O(n^2). The space complexity is O(1) excluding the output array, as only a few pointers and temporary storage for triplets are used. This analysis aligns with the provided complexities and highlights that extra memory is minimal beyond storing results.
What Interviewers Usually Probe
- Do you see how sorting simplifies duplicate management in two-pointer scanning?
- Can you explain why moving both pointers inward maintains the sum invariant?
- Will you handle cases with multiple zeros or repeated numbers correctly?
Common Pitfalls or Variants
Common pitfalls
- Failing to skip duplicate fixed elements leads to repeated triplets in output.
- Not advancing pointers past duplicate values after finding a triplet can cause repeated results.
- Assuming unsorted arrays allow direct two-pointer scans without first sorting, breaking the invariant logic.
Follow-up variants
- Find all triplets that sum to a specific target value instead of zero, still avoiding duplicates.
- Return the count of unique triplets instead of the actual triplet arrays, focusing on optimization.
- Extend to 4Sum by fixing two elements and using two-pointer scanning for the remaining pair, managing duplicates carefully.
How GhostInterview Helps
- Capture the array input or screen to provide precise triplet tracing.
- Guide the two-pointer path, show which sums are checked, and explain time O(n^2) and space O(1) complexities.
- Support live debugging through screen-share, highlighting fixed elements and pointer movements to verify uniqueness of triplets.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What pattern does 3Sum primarily use?
3Sum leverages two-pointer scanning with invariant tracking after sorting the array, allowing systematic sum checks and duplicate management.
How do I avoid duplicate triplets in 3Sum?
Skip duplicate elements when fixing the first number and after finding valid triplets, move left and right pointers past identical values to maintain uniqueness.
Can 3Sum handle arrays with multiple zeros?
Yes, the algorithm naturally handles multiple zeros by skipping duplicates while scanning, ensuring only unique triplets like [0,0,0] are included once.
Why is sorting necessary in 3Sum?
Sorting ensures that the two-pointer scan works correctly, enabling deterministic pointer movements and simplifying duplicate detection to prevent repeated triplets.
What is the time and space complexity of 3Sum?
The overall time complexity is O(n^2) due to nested loops with two-pointer scanning, and space complexity is O(1) excluding the output list storing the triplets.
Need direct help with 3Sum instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture 3Sum from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find the sum of three integers in an array that is closest to a given target using two-pointer scanning.
Open problem page#18 4SumThe 4Sum problem requires finding all unique quadruplets in an array that sum to a specific target value.
Open problem page#75 Sort ColorsSort Colors requires in-place reordering of an array using a two-pointer scanning strategy to group 0s, 1s, and 2s efficiently.
Open problem page