3Sum Problem Solution - Efficient Algorithm for Finding Triplets

The 3Sum problem requires finding all unique triplets in an array that sum to zero. This classic algorithmic challenge demonstrates the power of two-pointer techniques and careful duplicate handling in array processing.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. What are the constraints on the input array size? (e.g., is it bounded by 10⁴, 10⁶?)
2. Are duplicate triplets allowed in the output? If so, should we return all unique triplets or can duplicates exist?
3. Can we modify the input array in-place? (This affects space complexity trade-offs)
4. What is the expected return format? Should we return a list of lists or a set?
5. For follow-up, what time complexity are we aiming for? O(n²) is the target, but can we do better?

Restate the pattern or problem type in your own words: The 3Sum problem asks us to find all unique triplets in an array that sum to zero. It's a classic variation of the "Two Sum" problem, but extended to three elements with the additional constraint that we must avoid duplicate triplets in our result.

Clarify the signal words and constraint shape that point to it:

• "Three elements" or "triplets" in an array
• "Sum to zero" or "sum to target"
• "Unique triplets" or "no duplicates in output"
• Arrays with potentially negative numbers (which makes the problem non-trivial)
• Large input sizes that require efficient algorithms

Note any assumptions you are making:

• The array can be modified (we'll use sorting and two-pointer technique)
• We're looking for triplets, not individual elements
• The array may contain duplicates, but we want unique combinations in the result

Identify whether the pattern is best suited for static, streaming, or online scenarios: This pattern is primarily designed for static input scenarios where the entire array is available upfront. It's not naturally suited for streaming data because we need to process all elements together to find triplets that sum to zero. The problem benefits from sorting the array first, which is a batch operation rather than an online processing pattern.

The 3Sum problem is a canonical example of the "Three Sum" pattern, where we're looking for combinations of three elements that satisfy a specific sum condition. It's a fundamental problem in algorithmic interviews and demonstrates the use of sorting combined with two-pointer techniques to reduce time complexity from O(n³) to O(n²).

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Find three numbers..." or "triplets" in array
• "Sum equals target" or "sum to zero"
• Array input with size constraint (typically 3 or more elements)
• Need to return all unique triplets that satisfy condition
• Often includes "return all combinations" or "find all valid triplets"

Why this pattern fits better than the most common alternatives: This is fundamentally a variation of the classic "Two Sum" problem, but extended to three elements. The key insight is that we can reduce the 3Sum problem to a series of 2Sum problems by fixing one element and solving for the remaining two. This is more efficient than brute force O(n³) approach, which would check every possible triplet combination.

Compared to other approaches:

• Brute force O(n³): Checks all triplets, inefficient for large inputs
• Hash-based O(n²): Could work but requires careful handling of duplicates and is more complex
• Two-pointer O(n²): Clean, intuitive, and optimal for this specific constraint

Conditions where a variation or related pattern applies instead:

• If the problem asks for "any" triplet that sums to target (not all unique triplets), we can use a simpler hash-based approach
• If the problem involves "k-sum" where k > 3, we'd use a recursive approach or nested loops
• If the array is already sorted and we're looking for specific sum conditions, two-pointer technique becomes even more natural

The core insight that makes this pattern work: By fixing one element and applying two-pointer technique on the remaining subarray, we can efficiently find all valid triplets while avoiding duplicates. The key is to sort the array first to enable the two-pointer approach and to skip duplicate elements during iteration to ensure uniqueness of results.

3. Approach Evolution

Interview communication script:

My first instinct is to use a brute force approach where I check every possible triplet combination, which would be O(n³) time complexity. But that's inefficient because we're checking many redundant combinations. Let me think about how to optimize this.

I notice that if I sort the array first, I can use a two-pointer technique to find triplets efficiently. If I fix one element and then use two pointers to find the other two elements that sum to the negative of the fixed element, I can reduce the time complexity significantly.

I notice that if I maintain the invariant that my array is sorted, and I fix one element at a time from left to right, then for each fixed element I can use two pointers starting from the next position and the end of the array to find valid pairs. This way I avoid checking all combinations.

The key insight is that once the array is sorted, for any fixed element at index i, if I want to find two numbers that sum to -nums[i], I can use two pointers: one starting from i+1 and another from the end of array. If their sum is less than target, I move left pointer right; if greater, I move right pointer left. This gives me O(n) for the two-pointer search.

Let me walk through this approach step by step:

Brute-force approach: Check every triplet (i,j,k) where i < j < k and nums[i] + nums[j] + nums[k] = 0. This is O(n³) time and O(1) space, but it's inefficient because we're doing redundant work.

Improved approach: Sort the array first (O(n log n)), then for each element at index i, use two pointers to find pairs that sum to -nums[i]. This reduces the time complexity to O(n²) and space remains O(1) if we don't count the output.

Final approach:

1. Sort the array to enable two-pointer technique and early pruning
2. For each element from left to right (up to n-2):
   • Skip duplicates for the first element to avoid duplicate triplets
   • Use two pointers (left = i+1, right = n-1) to find pairs that sum to -nums[i]
   • When we find a valid triplet, add it to result and skip duplicates for second and third elements
3. This maintains the invariant that we're checking each possible combination exactly once

The key invariants that must hold:

• The array is sorted so we can use two pointers effectively
• For any fixed element at index i, we only look for pairs in the range [i+1, n-1]
• We skip duplicate elements to avoid duplicate triplets in the result
• Two pointers move toward each other until they meet

This approach is optimal for this problem as we need to find all valid triplets, so O(n²) is the best we can achieve for time complexity.

4. Data Structure Choice

For the 3Sum problem, I'll use a combination of data structures to achieve optimal performance:

Primary Data Structures:

1. Array/List - The input array is the primary data structure that holds the integers. Since we're looking for triplets that sum to zero, we need to be able to access elements by index and iterate through them systematically.

2. HashSet - Used in the two-pointer approach to store elements we've seen so far, enabling O(1) lookup time when searching for the third element that would complete a valid triplet.

3. ArrayList - Used to store and return the resulting triplets. This allows us to dynamically collect results as we find valid combinations.

Why Each Data Structure Is Needed:

• Array/List: Essential for maintaining the input data and enabling sorting operations. The array serves as our foundation for applying the two-pointer technique.

• HashSet: Crucial for optimizing lookup operations in the two-pointer approach. Without it, we'd need O(n) time to search for the third element, making our overall solution O(n³). The HashSet reduces this to O(1) average case.

• ArrayList: Necessary for collecting and returning the results. Since we don't know how many valid triplets will be found beforehand, a dynamic container like ArrayList is ideal.

Time and Space Impact:

• Time Complexity:

  • Sorting the array takes O(n log n)
  • The two-pointer approach runs in O(n²)
  • HashSet operations are O(1) average case
  • Overall time complexity: O(n²)

• Space Complexity:

  • Sorting requires O(log n) space (depending on implementation)
  • HashSet uses O(n) space in worst case
  • ArrayList for results uses O(k) where k is the number of valid triplets
  • Overall space complexity: O(n)

Helper Structures:

• Two Pointers: While not a traditional data structure, the left and right pointer variables maintain our search boundaries during the two-pointer traversal. They're essential for efficiently finding triplets without nested loops.

This combination provides an optimal balance between time efficiency and space usage for the 3Sum problem, avoiding the O(n³) brute force approach while maintaining clean, readable code structure.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step by step.

Example: nums = [-1, 0, 1, 2, -1, -4]

Step 1: Sort the array to enable two-pointer technique and easier duplicate handling.

• After sorting: [-4, -1, -1, 0, 1, 2]

Step 2: Fix the first element and use two pointers for remaining elements.

• i = 0, fix nums[0] = -4
• Left pointer: 1, Right pointer: 5 (last index)
• Sum = -4 + (-1) + 2 = -3 (too small, move left pointer right)
• Sum = -4 + 0 + 2 = -2 (too small, move left pointer right)
• Sum = -4 + 1 + 2 = -1 (too small, move left pointer right)
• Left pointer reaches right pointer, so no valid pairs for i=0

Step 3: Move to next element and skip duplicates.

• i = 1, nums[1] = -1 (same as previous, skip to avoid duplicate triplets)
• i = 2, fix nums[2] = -1
• Left pointer: 3, Right pointer: 5
• Sum = -1 + 0 + 2 = 1 (too large, move right pointer left)
• Sum = -1 + 0 + 1 = 0 (found valid triplet: [-1, 0, 1])
• Add to result: [(-1, 0, 1)]
• Move left pointer right (skip duplicates)

Step 4: Continue with remaining elements.

• i = 3, fix nums[3] = 0
• Left pointer: 4, Right pointer: 5
• Sum = 0 + 1 + 2 = 3 (too large, move right pointer left)
• No more valid pairs for i=3

Step 5: Final result.

• Return: [[-1, 0, 1]]

The key insight is that by fixing one element and using two pointers on the remaining sorted array, we can efficiently find all triplets that sum to zero while avoiding duplicates by skipping repeated elements at each position.

The algorithm terminates correctly because:

1. We process each element as the first element of a triplet once
2. The two-pointer technique ensures we check all combinations efficiently
3. Skipping duplicates prevents redundant work and ensures unique triplets in output

6. Java Solution

import java.util.*;

public class ThreeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        // Handle edge case of null or insufficient input
        if (nums == null || nums.length < 3) {
            return new ArrayList<>();
        }
        
        // Sort the array to enable two-pointer technique and easy duplicate handling
        Arrays.sort(nums);
        
        List<List<Integer>> result = new ArrayList<>();
        
        // Iterate through each element as the first element of potential triplet
        for (int i = 0; i < nums.length - 2; i++) {
            // Skip duplicate values for the first element to avoid duplicate triplets
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            
            // Use two pointers to find remaining two elements
            int left = i + 1;
            int right = nums.length - 1;
            
            while (left < right) {
                int currentSum = nums[i] + nums[left] + nums[right];
                
                if (currentSum == 0) {
                    // Found a valid triplet
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    
                    // Skip duplicates for the second element
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    
                    // Skip duplicates for the third element
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    
                    // Move both pointers inward
                    left++;
                    right--;
                } else if (currentSum < 0) {
                    // Sum is too small, move left pointer to increase sum
                    left++;
                } else {
                    // Sum is too large, move right pointer to decrease sum
                    right--;
                }
            }
        }
        
        return result;
    }
}

This solution uses the classic two-pointer technique after sorting the input array. The key insight is that for any fixed first element, we can efficiently search for pairs that sum to the negative of that element using two pointers. The sorting step enables both efficient searching and easy duplicate elimination.

The algorithm maintains three invariants:

1. The outer loop index i always points to a unique first element (after skipping duplicates)
2. The two-pointer search always maintains left < right
3. When a valid triplet is found, both pointers are advanced past duplicates to avoid redundant results

7. Complexity Analysis

Time Complexity: O(n²)

The algorithm uses a two-pointer technique after sorting the array. The sorting step takes O(n log n) time, but the dominant term comes from the nested iteration: the outer loop runs O(n) times and for each iteration, the two-pointer search runs in O(n) time in the worst case. Therefore, the overall time complexity is O(n²).

Space Complexity: O(1)

The space complexity is constant because we only use a fixed number of variables for indices and temporary storage. The sorting operation may use O(log n) space depending on the implementation of the sorting algorithm (e.g., Java's Arrays.sort() uses a variant of quicksort or mergesort), but this is typically considered part of the input's space and not counted toward the algorithm's auxiliary space complexity.

Why These Bounds Are Correct

The time bound is tight because we must examine each potential triplet at least once to ensure no valid combinations are missed. The two-pointer technique ensures we don't revisit elements unnecessarily, achieving optimal linear search for each fixed element.

The space bound is tight because we only maintain a constant number of integer variables (left, right, i) and do not use any data structures that grow with input size. The sorting overhead is considered part of the problem setup rather than the algorithm's space usage.

Optimality

This solution is near-optimal for the 3Sum problem. While there are theoretical algorithms that can solve it in O(n²) time with better constants, no known algorithm can achieve better than O(n²) time complexity for the general case. The solution is optimal in terms of both time and space complexity for this problem.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Should return empty result list. Handle nums.length < 3 case immediately.
• Arrays with fewer than 3 elements: Same as above - no valid triplets possible.
• Arrays with exactly 3 elements: Need to check if their sum equals zero.

Duplicate Values and Repeated States

• Duplicate triplets in output: Must avoid returning identical triplets. The key is to skip duplicates during iteration after sorting.
• Handling duplicate elements: When nums[i] == nums[i-1], skip to avoid duplicate triplets.
• Duplicate handling in two-pointer approach: When left and right pointers find a valid triplet, still need to skip duplicates on both sides.

Boundary Conditions

• All positive numbers: No valid triplets since sum of three positives is always positive.
• All negative numbers: No valid triplets since sum of three negatives is always negative.
• Large numbers and overflow: Though Java's int handles reasonably large values, ensure that sum calculations don't overflow (though unlikely in typical test cases).
• Zeroes: Arrays like [0, 0, 0] are valid and should return [[0, 0, 0]].

Common Implementation Mistakes

• Not sorting first: Without sorting, the two-pointer technique fails to work correctly.
• Skipping too aggressively: Skipping duplicates in a way that misses valid combinations or skips valid triplets.
• Not handling the case where all elements are same: E.g., [0, 0, 0, 0] or [-1, -1, -1].
• Incorrect loop bounds: Forgetting that the outer loop should go up to nums.length - 2 to allow space for two other elements.
• Not advancing pointers correctly: When a valid triplet is found, both left and right must be moved to avoid infinite loops or missing valid combinations.

Example Edge Cases

• [0, 0, 0] → [[0, 0, 0]]
• [1, 2, -3] → [[1, 2, -3]]
• [0, 0, 0, 0] → [[0, 0, 0]]
• [-1, 0, 1, 2, -1, -4] → [[−1, −1, 2], [−1, 0, 1]] (duplicates in input)
• [2, 7, 11, 15] → [] (no valid triplets)
• [0, 0, 0, 1, 2] → [[0, 0, 0]]

9. Alternative Approaches

There are several alternative approaches to solving the 3Sum problem, each with different trade-offs:

Brute Force Approach: The most straightforward approach is to use three nested loops to check every possible triplet combination. This results in O(n³) time complexity and O(1) space complexity. While simple to implement, this approach is inefficient for large inputs and doesn't leverage any structural properties of the problem.

Hash Set Approach: We can optimize the brute force approach by using a hash set to store elements and reduce one loop. For each pair (i,j), we compute the third element needed to sum to zero and check if it exists in our set. This approach has O(n²) time complexity but requires O(n) space for the hash set, and it's more complex to handle duplicates properly.

Two Pointers with Sorting: This is the preferred approach we've implemented, but an alternative is to sort the array first and then for each element, use two pointers to find pairs that sum to the negative of that element. This approach also has O(n²) time complexity but uses only O(1) extra space (excluding the output), making it more memory-efficient than hash-based solutions.

Binary Search Approach: After sorting, for each pair (i,j), we can use binary search to find if the third element exists. This approach has O(n² log n) time complexity due to the binary search, making it less efficient than our two-pointer approach.

The hash set approach is particularly useful when we need to handle arrays with many duplicates efficiently, while the two-pointer approach is preferred for its optimal time complexity and minimal space usage. Our chosen solution strikes the best balance between simplicity, efficiency, and memory usage for most practical scenarios.

10. Test Cases

public class ThreeSumTestCases {
    public static void main(String[] args) {
        // Test case 1: Basic example from problem description
        int[] nums1 = {-1, 0, 1, 2, -1, -4};
        // Expected: [[-1,-1,2], [-1,0,1]]
        
        // Test case 2: No valid triplets
        int[] nums2 = {0, 1, 1};
        // Expected: []
        
        // Test case 3: All zeros
        int[] nums3 = {0, 0, 0};
        // Expected: [[0,0,0]]
        
        // Test case 4: Empty array
        int[] nums4 = {};
        // Expected: []
        
        // Test case 5: Array with less than 3 elements
        int[] nums5 = {1, 2};
        // Expected: []
        
        // Test case 6: Large numbers
        int[] nums6 = {1000000000, 1000000000, 1000000000};
        // Expected: []
        
        // Test case 7: Mixed positive and negative
        int[] nums7 = {-2, 0, 1, 1, 2};
        // Expected: [[-2,0,2], [-2,1,1]]
        
        // Test case 8: Duplicates in result
        int[] nums8 = {-2, 0, 0, 2, 2};
        // Expected: [[-2,0,2]]
    }
}

Sample test cases include:

1. Basic case: [-1, 0, 1, 2, -1, -4] → [[-1,-1,2], [-1,0,1]]
2. No solution: [0, 1, 1] → []
3. All zeros: [0, 0, 0] → [[0,0,0]]
4. Edge case - empty: [] → []
5. Edge case - too small: [1, 2] → []
6. Large numbers: [1000000000, 1000000000, 1000000000] → []
7. Mixed values: [-2, 0, 1, 1, 2] → [[-2,0,2], [-2,1,1]]
8. Duplicate handling: [-2, 0, 0, 2, 2] → [[-2,0,2]]

The tricky case involves handling duplicate triplets in the output while ensuring no duplicates in the result set. The boundary case tests arrays with fewer than 3 elements to ensure proper handling of edge conditions.

11. Final Summary

The core idea is to transform the 3Sum problem into a more manageable 2Sum subproblem by fixing one element and using two pointers to find pairs that sum to the negative of the fixed element. This approach works efficiently by leveraging sorting to enable binary search-like two-pointer technique, achieving O(n²) time complexity which is optimal for this problem since we must examine at least O(n²) potential triplets. The solution's efficiency comes from avoiding redundant checks through careful pointer movement and duplicate handling, making it both time and space optimal for the given constraints.