Problem: 3Sum - Finding Unique Triplets | MANG Interview Problem Bank

1. Problem Statement

Mental Model

Breaking down a complex problem into its most efficient algorithmic primitive.

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.

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

2. The Mental Model: "Fix and Squeeze"

Solving 3Sum is essentially solving the Two Sum II problem multiple times.

Reduce to 2Sum: If we "fix" one number (let's say nums[i]), the problem becomes: "Find two other numbers nums[j] and nums[k] such that nums[j] + nums[k] == -nums[i]."
Use Two Pointers: By sorting the array first, we can find those two numbers in $O(N)$ using the Squeeze pattern.
Handle Duplicates: Since the array is sorted, duplicates are adjacent. We just need to skip any number that is the same as the one we just processed.

3. Visual Execution (Triple Convergence)

graph LR
    Start[-4, -1, -1, 0, 1, 2] --> Fixed[Fix -1 at index 1]
    Fixed --> Squeeze[Search in: -1, 0, 1, 2 for Sum=1]
    Squeeze --> Found1[L: -1, R: 2 | Sum: 1 - YES!]
    Squeeze --> Found2[L: 0, R: 1 | Sum: 1 - YES!]
    Found2 --> Duplicate[Skip next -1 to avoid duplicate triplet]

4. Java Implementation (Optimal O(N^2))

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    // 1. Mandatory Sort: O(N log N)
    Arrays.sort(nums);
    
    for (int i = 0; i < nums.length - 2; i++) {
        // 2. Skip duplicate fixed elements
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        
        int target = -nums[i];
        int left = i + 1;
        int right = nums.length - 1;
        
        // 3. Two-pointer Squeeze
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                
                // 4. Critical: Skip duplicate left and right elements
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return res;
}

5. Verbal Interview Script (Staff Tier)

Interviewer: "How do you ensure you don't return duplicate triplets?"

You: "Managing duplicates is the hardest part of this problem. By Sorting the array at the beginning, I gain two advantages. First, I can use the $O(N)$ Two-Pointer technique instead of an $O(N)$ HashSet, keeping space at $O(1)$. Second, I can handle duplicates greedily. I use if (i > 0 && nums[i] == nums[i-1]) continue to ensure I don't 'fix' the same number twice. Inside the while loop, once a valid triplet is found, I increment the left and decrement the right pointers until they point to different values. This ensures that every triplet in the result is unique without needing a heavy HashSet<List<Integer>> for deduplication."

6. Staff-Level Follow-Ups

Follow-up 1: "What is the time complexity if the array is already sorted?"

The Answer: "It would be $O(N^2)$. Sorting is just $O(N \log N)$, so the nested loop structure of the 'Fix and Squeeze' approach is the actual bottleneck."

Follow-up 2: "Can you solve this in O(N)?"

The Answer: "No. It has been mathematically proven that the 3Sum problem has a lower bound of $O(N^2)$ (or slightly less with extremely complex algorithms). Any solution involving finding all unique triplets will require at least quadratic time."

7. Performance Nuances (The Java Perspective)

List vs. Arrays: Arrays.asList() is convenient, but it creates a small wrapper object. In a high-throughput system, you might return a flat int[] or use a primitive-specialized collection to save memory.
Early Exit: If nums[i] > 0, we can break the entire loop. Since the array is sorted, any subsequent nums[left] and nums[right] will also be $> 0$, making a sum of zero impossible. This is a great "Senior" optimization to mention.

6. Staff-Level Verbal Masterclass (Communication)

Interviewer: "How would you defend this specific implementation in a production review?"

You: "In a mission-critical environment, I prioritize the Big-O efficiency of the primary data path, but I also focus on the Predictability of the system. In this implementation, I chose a iterative two-pointer approach. While a recursive solution is more readable, I would strictly monitor the stack depth. If this were to handle skewed inputs, I would immediately transition to an explicit stack on the heap to avoid a StackOverflowError. From a memory perspective, I leverage primitive arrays to ensure that we minimize the garbage collection pauses (Stop-the-world) that typically plague high-throughput Java applications."

7. Global Scale & Distributed Pivot

When a problem like this is moved from a single machine to a global distributed architecture, the constraints change fundamentally.

Data Partitioning: We would shard the input space using Consistent Hashing. This ensures that even if our dataset grows to petabytes, any single query only hits a small subset of our cluster, maintaining logarithmic lookup times.
State Consistency: For problems involving state updates (like DP or Caching), we would use a Distributed Consensus protocol like Raft or Paxos to ensure that all replicas agree on the final state, even in the event of a network partition (The P in CAP theorem).

8. Performance Nuances (The Staff Perspective)

Cache Locality: Accessing a 2D matrix in row-major order (reading [i][j] then [i][j+1]) is significantly faster than column-major order in modern CPUs due to L1/L2 cache pre-fetching. I always structure my loops to align with how the memory is physically laid out.
Autoboxing and Generics: In Java, using List<Integer> instead of int[] can be 3x slower due to the overhead of object headers and constant wrapping. For the most performance-sensitive sections of this algorithm, I advocate for primitive specialized structures.

Key Takeaways

The Answer: "It would be $O(N^2)$. Sorting is just $O(N \log N)$, so the nested loop structure of the 'Fix and Squeeze' approach is the actual bottleneck."
The Answer: "No. It has been mathematically proven that the 3Sum problem has a lower bound of $O(N^2)$ (or slightly less with extremely complex algorithms). Any solution involving finding all unique triplets will require at least quadratic time."
Problem: 4Sum (Generalized N-Sum Pattern)

Problem: 3Sum - Finding Unique Triplets