Blind 75Medium

3Sum — Sort Then Two-Pointer Search

Sort the array, fix one value, and sweep the remaining window with two pointers while skipping duplicates.

Two PointersSortingArray

View problem on LeetCode

Problem Statement

Return all unique triplets [nums[i], nums[j], nums[k]] such that the three numbers sum to zero.

Why This Problem Matters

Drills the transition from brute-force O(n^3) enumeration to the canonical O(n^2) two-pointer pattern.
Forces careful duplicate handling both on the fixed index and within the two-pointer loop.
Serves as a gateway to the general k-sum pattern used in many interview questions.

Thought Process

Sort to structure the search

With numbers in order you can leverage two pointers to move toward or away from zero efficiently.

Fix one element at a time

Iterate i across the array and treat nums[i] as the anchor, then reduce to a 2Sum on the suffix.

Skip duplicates aggressively

Avoid repeated work by skipping identical anchors and collapsing consecutive duplicate left/right values.

Step-by-Step Reasoning

Sort nums ascending.
Loop i from 0 while nums[i] <= 0; continue if i > 0 and nums[i] == nums[i - 1].
Set left = i + 1, right = n - 1; compute sum = nums[i] + nums[left] + nums[right].
If sum < 0 increase left; if sum > 0 decrease right; otherwise record the triplet and skip duplicates on both pointers.

Dry Run

i = 0, nums[i] = -4

Two-pointer scan finds no zero-sum pair with -4; move to next anchor.

i = 1, nums[i] = -1

Pairs (left=2,right=5) yield [-1,-1,2] and [-1,0,1] after skipping duplicates.

Complexity Analysis

Time

O(n^2)

Space

O(1)

Why

Sorting dominates at O(n log n); the subsequent two-pointer sweeps are quadratic.

Annotated Solution

JAVA

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeSum {
  public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();

    for (int i = 0; i < nums.length && nums[i] <= 0; i += 1) {
      if (i > 0 && nums[i] == nums[i - 1]) {
        continue;
      }

      int left = i + 1;
      int right = nums.length - 1;
      while (left < right) {
        int sum = nums[i] + nums[left] + nums[right];
        if (sum < 0) {
          left += 1;
        } else if (sum > 0) {
          right -= 1;
        } else {
          result.add(Arrays.asList(nums[i], nums[left], nums[right]));
          while (left < right && nums[left] == nums[left + 1]) {
            left += 1;
          }
          while (left < right && nums[right] == nums[right - 1]) {
            right -= 1;
          }
          left += 1;
          right -= 1;
        }
      }
    }

    return result;
  }
}

Sorting exposes ordering so you can shrink toward zero from both ends. Duplicate guards around i, left, and right ensure each triplet is unique.

Common Pitfalls

Forgetting to skip duplicate anchors leads to repeated triplets.
Moving only one pointer after finding a valid triplet can keep producing the same combination.
Stopping the loop when nums[i] == 0 misses the [0,0,0] case.

Follow-Up Questions

Generalise the approach to k-sum and discuss the complexity.
Return the count of unique triplets instead of listing them.

Key Takeaways

Transform multi-sum problems into simpler subproblems by fixing part of the combination.

Sorting plus duplicate skipping is the standard way to control result cardinality.

Understand why moving the wrong pointer loses potential pairs before the interview.