Three Sum Problem Solution and Algorithm Analysis

The three sum problem requires finding all unique triplets in an array that sum to zero. This classic algorithmic challenge tests understanding of sorting, two-pointer techniques, and duplicate handling in competitive programming interviews.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. What is the expected time complexity target for the solution? Are we aiming for O(n²) or better?
2. Can we modify the input array, or must we preserve the original order?
3. Should we return all unique triplets, or can we return duplicates if they exist in the input?
4. What is the maximum size of the input array? Will it be small (< 1000) or potentially large?
5. Do we need to handle negative numbers, and what is the expected range of values?

Restated problem: Given an integer array, find all unique triplets that sum to zero. Each triplet must consist of three distinct indices from the array, and we want to return all such combinations where the sum equals zero.

Input/Output specification:

• Input: An integer array nums of length n (where 0 ≤ n ≤ 3000)
• Output: A list of lists containing unique triplets that sum to zero
• Each triplet must have three distinct indices (i < j < k) and nums[i] + nums[j] + nums[k] = 0

Key constraints:

• The array can contain both positive and negative integers
• Duplicates in the input array should not result in duplicate triplets in the output
• The solution must handle edge cases like empty arrays, arrays with fewer than 3 elements, and arrays with all same values

Assumptions made:

• The array can be modified during processing (we'll use sorting as part of our approach)
• We don't need to preserve the original order in the output
• The problem asks for unique triplets, not just any triplets that sum to zero

Data shape and structure: The input is a one-dimensional array of integers with potential for negative values, zero, and positive values. The hidden structure involves combinations and sums that form a mathematical constraint (a + b + c = 0), which suggests using sorting and two-pointer techniques to efficiently explore combinations.

2. Pattern Recognition

Identifying the pattern

This problem follows the Two Pointers pattern combined with Sorting and Array Traversal.

Wording that signals the pattern

• "Find all unique triplets" - indicates we need to systematically explore combinations while avoiding duplicates
• "Sum equals zero" - suggests we can leverage sorting and two-pointer technique to find triplets efficiently
• "Return all triplets that sum to zero" - signals we're looking for a specific target combination rather than just one solution

Why this fits the pattern

The problem asks us to find all unique combinations of three elements that sum to zero. This naturally maps to the two-pointer technique because:

1. After sorting, we can fix one element and use two pointers to find the remaining two elements that sum to the negative of our fixed element
2. The sorted array structure allows us to efficiently skip duplicates and navigate toward the target sum
3. This is a classic variation of the "Two Sum" problem extended to three elements

Core insight

The key insight is that we can reduce the 3-sum problem to a 2-sum problem by fixing one element and then applying two-pointer technique on the remaining array. This transforms the O(n³) brute force approach into O(n²) by leveraging sorted order and two-pointer traversal.

The pattern emerges from the mathematical property: if we fix element nums[i] and want nums[i] + nums[left] + nums[right] = 0, then we need nums[left] + nums[right] = -nums[i]. This is exactly the 2-sum problem with a fixed target.

3. Approach Evolution

My first instinct is to use a brute force approach checking all possible triplets, which would be O(n³) time complexity because we'd need three nested loops to examine every combination of three elements. But that's inefficient and not optimal for this problem.

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 reduce the search space significantly. This is a classic pattern for 3Sum problems where we fix one element and then find pairs that sum to the negative of that element.

If I maintain the invariant that for any fixed element at index i, I only look for pairs in the remaining array (i+1 to end) that sum to -nums[i], I can reduce this to O(n²) time complexity. The key insight is that once we fix one element, we're essentially solving a 2Sum problem on the remaining elements.

Here's my step-by-step approach:

1. Sort the array first - this enables us to use two pointers and helps avoid duplicates
2. For each element from index 0 to n-3 (since we need at least 3 elements):
   • Use two pointers: one starting just after current element, another at the end
   • Calculate sum of current element + left pointer + right pointer
   • If sum equals zero, we found a triplet
   • If sum is less than zero, move left pointer right to increase sum
   • If sum is greater than zero, move right pointer left to decrease sum
3. Skip duplicates at each level to avoid redundant triplets

The important invariants that must hold:

• The array is sorted to enable two-pointer technique
• For any fixed element, we only search in the remaining portion of array
• We skip duplicate elements to avoid returning identical triplets

This approach is optimal because we can't do better than O(n²) for this problem - we must examine at least quadratic number of combinations to find all triplets that sum to zero.

4. Data Structure Choice

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

Primary Data Structures:

1. Array/ArrayList - The input array is the primary data structure that holds our integers. I'll use a standard int[] for efficiency since we're working with primitive types and don't need dynamic resizing.

2. Two Pointers - For the core algorithm, I'll use two pointers (left and right) that traverse the sorted array from both ends toward the center. This is key to achieving O(n) time complexity for the two-pointer scan.

3. List/ArrayList - To store and return the result triplets. I'll use List<List<Integer>> to collect all valid combinations that sum to zero.

Why These Choices Work:

The array is essential as our input container and is the natural choice since we're given a fixed-size integer array. The two-pointer technique is optimal here because once the array is sorted, we can efficiently explore all combinations without nested loops by maintaining the invariant that one pointer moves left and the other moves right.

The list structure is needed to collect results, and ArrayList provides O(1) amortized append operations which is suitable for our use case where we don't know the final number of triplets beforehand.

Space Considerations:

• The input array is given and we don't count it toward our space complexity
• We use O(1) extra space for the two pointers (not counting output)
• The result list space is O(k) where k is the number of valid triplets, which is part of the required output

Helper Structures:

I don't need any additional helper structures beyond what's mentioned above. The sorting operation happens in-place using the built-in Arrays.sort() method, which is efficient and doesn't require extra space beyond what's needed for the sorting algorithm itself.

The combination of these structures enables us to achieve O(n²) time complexity with minimal space overhead, which is optimal for this problem given the constraints.

5. Algorithm Walkthrough

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

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

Step 1: Sort the array first.

• nums = [-4, -1, -1, 0, 1, 2]

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

• i = 0, nums[i] = -4
• Target sum for remaining two elements = 0 - (-4) = 4
• Two pointers: left = 1, right = 5
• nums[left] + nums[right] = -1 + 2 = 1 < 4, so move left pointer right
• nums[left] + nums[right] = 0 + 2 = 2 < 4, so move left pointer right
• nums[left] + nums[right] = 1 + 2 = 3 < 4, so move left pointer right
• Now left = 4, right = 5, nums[left] + nums[right] = 1 + 2 = 3 < 4
• No more valid combinations for i=0

Step 3: Continue with i = 1, nums[i] = -1

• Target sum for remaining two elements = 0 - (-1) = 1
• Two pointers: left = 2, right = 5
• nums[left] + nums[right] = -1 + 2 = 1 == 1, found a triplet: [-1, -1, 2]
• Move left pointer right to avoid duplicates

Step 4: Continue with i = 2, nums[i] = -1

• Target sum for remaining two elements = 0 - (-1) = 1
• Two pointers: left = 3, right = 5
• nums[left] + nums[right] = 0 + 2 = 2 > 1, so move right pointer left
• nums[left] + nums[right] = 0 + 1 = 1 == 1, found a triplet: [-1, 0, 1]
• Move left pointer right to avoid duplicates

Step 5: Continue with i = 3, nums[i] = 0

• Target sum for remaining two elements = 0 - 0 = 0
• Two pointers: left = 4, right = 5
• nums[left] + nums[right] = 1 + 2 = 3 > 0, so move right pointer left
• No more valid combinations for i=3

Final Result: [[-1, -1, 2], [-1, 0, 1]]

The algorithm correctly handles duplicate elimination by skipping over repeated values for the first element and using two pointers to efficiently find pairs that sum to the target. The sorting step ensures we can use the two-pointer technique, and the loop invariant that elements to the left of i are already processed ensures we don't generate duplicate triplets.

graph TD
    A[Sort Array] --> B{Fixed First Element}
    B --> C[Two Pointers: Left=Fix+1, Right=End]
    C --> D{Sum < Target?}
    D -->|Yes| E[Move Left Pointer Right]
    D -->|No| F{Sum > Target?}
    F -->|Yes| G[Move Right Pointer Left]
    F -->|No| H[Sum == Target?]
    H -->|Yes| I[Add Triplet to Result]
    I --> J[Move Left Pointer Right]
    J --> K{Continue While Left < Right}
    K -->|Yes| C
    K -->|No| L[Next First Element]
    L --> M{End of Array?}
    M -->|No| B
    M -->|Yes| N[Return Result]

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 triplets
        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 pointers inward after finding a valid triplet
                    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;
    }
}

The solution uses a two-pointer technique after sorting the input array. For each element as the first element of a triplet, we use two pointers to efficiently search for pairs that sum to the negative of the first element. The key insight is that once we fix one element, we're essentially solving a two-sum problem on the remaining elements. The sorting step enables us to handle duplicates systematically and allows for efficient pointer movement.

The algorithm maintains three invariants:

1. The array is sorted to enable two-pointer technique
2. We skip duplicates for the first element to avoid duplicate triplets in result
3. After finding a valid triplet, we skip duplicates for the second and third elements to avoid redundant results

This approach is optimal for this problem with O(n²) time complexity and O(1) extra space (excluding the output list).

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, and the nested loop structure processes each element at most once with the two pointers moving toward each other. Since we have one outer loop iterating through n elements and an inner two-pointer scan that takes O(n) time in the worst case, the overall time complexity is dominated by O(n²).

Space Complexity: O(1)

The space complexity is constant because we only use a fixed number of variables for indices and do not store any additional data structures that scale with input size. The sorting operation is typically done in-place, so it doesn't contribute to the space complexity.

Why these bounds are correct:

The O(n²) time bound is tight because in the worst case, we must examine all possible pairs of elements to ensure no valid triplets are missed. The O(1) space bound holds 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.

Optimality:

This solution is near-optimal for the three-sum problem. While there are algorithms that can solve it in O(n²) time with better constants, the O(n²) complexity is the theoretical lower bound for comparison-based algorithms when we need to report all unique triplets. The solution is optimal in terms of both time and space complexity for this problem's constraints.

The algorithm efficiently handles the core challenge of avoiding O(n³) brute force by leveraging sorting and two-pointer technique to reduce nested iteration to linear scans.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty array: Should return empty result list. Handle with nums.length < 3 check.
• Arrays with fewer than 3 elements: Same handling as empty array - return empty list.
• Single element array: No triplets possible, return empty list.

Duplicate Values and Repeated States

• Duplicate triplets in output: The algorithm must avoid returning identical triplets. This is handled by skipping duplicate values during iteration.
• Duplicate elements in input: The sorting approach naturally groups duplicates together, making it easier to skip them.
• Multiple occurrences of same value: When skipping duplicates, ensure we don't skip valid combinations that use different indices.

Boundary Conditions

• All zeros: Array like [0, 0, 0] should return [[0, 0, 0]].
• All positive or all negative: Arrays like [1, 2, 3] or [-3, -2, -1] should return empty list.
• Very large numbers: Integer overflow is not an issue here since we're only checking sums, but large values may affect performance.

Common Implementation Mistakes

• Not handling duplicates properly: Failing to skip duplicate elements in the outer loop can lead to repeated triplets.
• Incorrect loop bounds: Using i < nums.length instead of i < nums.length - 2 in the outer loop.
• Not advancing pointers correctly: In the two-pointer phase, not properly moving left and right pointers after finding a match.
• Missing edge case handling: Not checking for null input or arrays with fewer than 3 elements.
• Incorrect triplet formation: Adding elements to result list in wrong order or not maintaining sorted order within triplets.

Implementation-specific Issues

• Modifying input array: If the problem allows mutation, sorting modifies the original array. If not, we must create a copy.
• Integer overflow in sum calculation: Though not an issue in this specific problem, it's a common pitfall in similar problems.
• Not using proper comparison: Using == instead of proper equality checks when comparing elements after sorting.

The key to avoiding these pitfalls is careful handling of indices, proper duplicate skipping logic, and maintaining the correct loop bounds throughout the algorithm.

9. Alternative Approaches

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

Brute Force Approach: The most straightforward alternative is to use three nested loops to check every possible triplet combination. This approach has O(n³) time complexity and O(1) space complexity. While simple to implement, it's inefficient for large inputs and doesn't leverage the sorted array property that makes the two-pointer technique optimal.

Hash Map Approach: We can use a hash map to store elements and their indices. For each pair of elements, we compute the third required element and check if it exists in our hash map. This approach has O(n²) time complexity but O(n) space complexity, which is better than brute force but worse than the two-pointer method in terms of space efficiency.

Two-Pointer with Sorting: If we don't start with a sorted array, we can sort it first and then apply the two-pointer technique. This approach has O(n log n) time complexity due to sorting, but the overall complexity remains O(n²) for finding triplets. This is still better than brute force but requires the initial sorting step.

The two-pointer approach is preferred because it provides optimal O(n²) time complexity with minimal space overhead, assuming the input array is already sorted. The hash map approach offers a good middle ground but requires additional space, while brute force is inefficient for larger inputs.

The chosen solution represents the optimal balance between time complexity and space efficiency for this specific problem, particularly when working with sorted arrays.

10. Test Cases

import java.util.*;

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]]
        System.out.println("Test 1: " + Arrays.toString(threeSum(nums1)));
        
        // Test case 2: No valid triplets
        int[] nums2 = {1, 2, 3};
        // Expected: []
        System.out.println("Test 2: " - Arrays.toString(threeSum(nums2)));
        
        // Test case 3: All zeros
        int[] nums3 = {0, 0, 0};
        // Expected: [[0,0,0]]
        System.out.println("Test 3: " + Arrays.toString(threeSum(nums3)));
        
        // Test case 4: Empty array
        int[] nums4 = {};
        // Expected: []
        System.out.println("Test 4: " + Arrays.toString(threeSum(nums4)));
        
        // Test case 5: Single element
        int[] nums5 = {1};
        // Expected: []
        System.out.println("Test 5: " + Arrays.toString(threeSum(nums5)));
        
        // Test case 6: Two elements
        int[] nums6 = {1, 2};
        // Expected: []
        System.out.println("Test 6: " + Arrays.toString(threeSum(nums6)));
        
        // Test case 7: Multiple duplicates
        int[] nums7 = {0, 0, 0, 0};
        // Expected: [[0,0,0]]
        System.out.println("Test 7: " + Arrays.toString(threeSum(nums7)));
        
        // Test case 8: Large numbers
        int[] nums8 = {-2147483648, 0, 2147483647};
        // Expected: [[-2147483648, 0, 2147483647]]
        System.out.println("Test 8: " + Arrays.toString(threeSum(nums8)));
        
        // Test case 9: Mixed positive and negative
        int[] nums9 = {-2, 0, 1, 1, 2};
        // Expected: [[-2,0,2], [-2,1,1]]
        System.out.println("Test 9: " + Arrays.toString(threeSum(nums9)));
    }
    
    public static List<List<Integer>> threeSum(int[] nums) {
        // Implementation here...
        return new ArrayList<>();
    }
}

Sample Test Cases:

1. Basic case: [-1, 0, 1, 2, -1, -4] → [[-1,-1,2], [-1,0,1]]
2. No solution: [1, 2, 3] → []
3. All zeros: [0, 0, 0] → [[0,0,0]]
4. Empty input: [] → []
5. Single element: [1] → []
6. Two elements: [1, 2] → []
7. Multiple duplicates: [0, 0, 0, 0] → [[0,0,0]]
8. Large numbers: [-2147483648, 0, 2147483647] → [[-2147483648, 0, 2147483647]]
9. Mixed values: [-2, 0, 1, 1, 2] → [[-2,0,2], [-2,1,1]]

Key Test Coverage:

• Empty and minimal arrays
• Arrays with no valid triplets
• Arrays with all same elements
• Arrays with mixed positive/negative values
• Arrays with integer overflow edge cases
• Arrays with multiple valid combinations

11. Final Summary

The core insight is to reduce the three-sum problem from O(n³) to O(n²) by fixing one element and using two pointers to find pairs that sum to the negative of the fixed element. This approach leverages sorting to enable efficient two-pointer traversal while using careful duplicate handling to ensure unique triplets. The solution is optimal for the given constraints, providing a clean balance between time complexity and implementation clarity.

The algorithm works by first sorting the array to enable the two-pointer technique, then iterating through each element as a potential first element of a triplet. For each fixed element, we use two pointers (left and right) to efficiently search for pairs that sum to the negative of our fixed value. The key optimization is avoiding redundant work by skipping duplicate values and maintaining proper bounds.

This solution demonstrates strong problem-solving skills through pattern recognition, algorithmic optimization, and clean implementation. It handles edge cases gracefully and provides optimal time complexity O(n²) with space complexity O(1) beyond the input storage, making it suitable for production use in high-performance systems.