Stage 1: Foundations·Two Pointers & Sliding Window

Medium#158 min readTwo PointersSortingLeetCode

3Sum

Sort + Two Pointers

Fix one element, two-pointer the rest. Duplicate handling is the real challenge.

Published Apr 15, 2026

Problem

Given an integer array nums, return all the unique triplets [nums[i], nums[j], nums[k]] such that:

i != j, i != k, j != k
nums[i] + nums[j] + nums[k] == 0

The solution set must not contain duplicate triplets.

Input

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

Output

[[-1,-1,2],[-1,0,1]]

Explanation

The duplicate -1 values must not produce duplicate triplets.

Input

nums = [0,1,1]

Output

[]

Input

nums = [0,0,0]

Output

[[0,0,0]]

Intuition

The brute-force version picks three indices and checks every triple. That is O(n^3), which is too slow even for moderate input sizes.

The useful reframe is to sort the array first. Once the numbers are sorted, the third value is no longer hidden. If you fix one number a, the remaining task becomes: find pairs b and c such that b + c = -a.

That is exactly a two-pointer problem on a sorted array. Move the left pointer right when the sum is too small, move the right pointer left when the sum is too large.

The real difficulty is not the search. It is duplicate control. The same numeric triplet can be discovered from multiple index combinations, so you must skip repeated values at every layer.

Approach

Sort + Two Pointers

TimeO(n^2)

SpaceO(log n)

Recommended

Sort the array, then iterate i from left to right.

Skip repeated values of nums[i]; the first occurrence of a value is enough.
Stop early once nums[i] > 0, because all later values are also nonnegative.
For each fixed nums[i], run a two-pointer search on the suffix i + 1...
After finding a valid triple, skip duplicate values on both sides before continuing.

This is the cleanest general solution because it uses the sorted order both for search and for deduplication.

impl Solution {
    pub fn three_sum(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
        nums.sort_unstable();
        let n = nums.len();
        let mut ans = Vec::new();

        for i in 0..n {
            if i > 0 && nums[i] == nums[i - 1] {
                continue;
            }
            if nums[i] > 0 {
                break;
            }

            let mut left = i + 1;
            let mut right = n.saturating_sub(1);

            while left < right {
                let sum= nums[i] + nums[left] + nums[right];

                if sum= 0 {
                    ans.push(vec![nums[i], nums[left], nums[right]]);
                    left = 1;
                    right -= 1;

                    while left < right && nums[left]= nums[left - 1] {
                        left = 1;
                    }
                    while left < right && nums[right]= nums[right + 1] {
                        right -= 1;
                    }
                } else if sum < 0 {
                    left = 1;
                } else {
                    right -= 1;
                }
            }
        }

        ans
    }
}

Rust · runnable

function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);
  const ans: number[][] = [];

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

    let left = i + 1;
    let right = nums.length - 1;

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];

      if (sum === 0) {
        ans.push([nums[i], nums[left], nums[right]]);
        left++;
        right--;

        while (left < right && nums[left] === nums[left - 1]) left++;
        while (left < right && nums[right] === nums[right + 1]) right--;
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }

  return ans;
}

TypeScript · runnable

Sorting is doing two jobs here. First, it turns the pair search into a monotone scan. Second, it makes duplicate elimination local and cheap.

Trace

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

i	fixed	left/right	sum	action
0	-4	-1, 2	-3	move left rightward
1	-1	-1, 2	0	record [-1,-1,2], then skip duplicates
1	-1	0, 1	0	record [-1,0,1], then advance both pointers

The outer loop fixes one value at a time; the inner loop only scans the suffix once.

Edge cases

All zeros should return one triple, not many.
Not enough numbers naturally yields an empty result.
Repeated values must be skipped both when fixing i and after finding a valid triple.
Positive fixed value can terminate the search early because the array is sorted.

💡

Tip

The two-pointer proof is the same one you will use for #11 Container With Most Water and #167 Two Sum II: when the array is sorted, moving one pointer changes the answer in a predictable direction.

Takeaway

Sort first when order is the obstacle.

For 3Sum, sorting converts a cubic search into a clean quadratic scan and gives you a principled way to remove duplicates instead of patching them after the fact.

Medium#167

Two Sum II - Sorted

Why does moving the left pointer increase the sum? Understand the proof.

Easy#125

Valid Palindrome

Converging pointers from both ends. Simple but builds the muscle memory.

Hard#76

Minimum Window Substring

The ‘hard’ sliding window — but if you understood #3, this is the same pattern with a counter.