Two Pointers

Back to DSA & Algorithms/00 - Roadmap Overview

What Are Two Pointers?

Two pointers is a technique where you use two variables (pointers) that move through a data structure (usually an array or string), reducing the need for nested loops.

Instead of checking every pair with O(n²), you cleverly move two pointers to find the answer in O(n).

Why It Works

The key insight: by moving pointers based on conditions, you eliminate large chunks of the search space at each step. You're not checking every combination — you're pruning intelligently.

Prerequisites

  • Most two-pointer problems require the array to be sorted first
  • If the array isn't sorted, you might need to sort it (adding O(n log n)) or use a different technique (hash map)

Pattern 1: Opposite Direction (Converging Pointers)

What it is

Place one pointer at the start, one at the end. Move them toward each other based on some condition.

When to use it

  • "Find two numbers that sum to target" (in a sorted array)
  • "Find the pair with maximum/minimum property"
  • "Is this string a palindrome?"
  • Anything involving pairs from both ends

The Mental Model

Imagine you're at a buffet table. You stand at one end, your friend stands at the other. You both walk toward the middle, and at each step, you compare what you see. If the sum of your plates is too heavy, the person with the heavier plate takes a lighter one (moves inward). If too light, the other person takes a heavier one.

Step-by-Step Walkthrough

java
// Problem: Two Sum II (sorted array)
// Input: numbers = [2, 7, 11, 15], target = 9

public int[] twoSumSorted(int[] numbers, int target) {
    int left = 0;                        // Start at the beginning
    int right = numbers.length - 1;      // Start at the end

    while (left < right) {
        int currentSum = numbers[left] + numbers[right];

        if (currentSum == target) {
            return new int[]{left, right};      // Found it!
        } else if (currentSum < target) {
            left++;                             // Sum too small → need bigger → move left forward
        } else {
            right--;                            // Sum too big → need smaller → move right backward
        }
    }

    return new int[]{};  // No solution found
}

// Walkthrough:
// left=0(2), right=3(15): sum=17 > 9 → right-- → right=2
// left=0(2), right=2(11): sum=13 > 9 → right-- → right=1
// left=0(2), right=1(7):  sum=9  = 9 → Found! Return [0, 1]

Why It's Correct

Because the array is sorted:

  • If sum < target: moving left right makes the sum larger (only way to increase)
  • If sum > target: moving right left makes the sum smaller (only way to decrease)
  • We never miss a valid pair because we only skip combinations that can't work

Container With Most Water

Problem: Given heights, find two lines that form a container holding the most water.

java
public int maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int maxWater = 0;

    while (left < right) {
        // Water limited by shorter line
        int width = right - left;
        int h = Math.min(height[left], height[right]);
        maxWater = Math.max(maxWater, width * h);

        // Move the shorter line inward (it's the bottleneck)
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }

    return maxWater;
}

// Why move the shorter line?
// The water is limited by the SHORTER line.
// Moving the taller line inward: width decreases, height can't increase → area decreases
// Moving the shorter line inward: width decreases, but height MIGHT increase → worth trying

Problems

Pattern 2: Same Direction (Fast & Slow Pointers)

What it is

Both pointers start at the same position and move in the same direction. One moves faster than the other. The slow pointer typically marks the "write position" or "boundary of processed elements".

When to use it

  • "Remove duplicates in-place"
  • "Remove specific elements in-place"
  • "Move zeros to the end"
  • "Detect cycle in linked list"

The Mental Model

Imagine two people reading the same book:

  • Fast reader scans ahead looking for interesting pages
  • Slow reader carefully copies only the good pages into a new notebook
  • The slow reader's notebook = your processed result

Step-by-Step Walkthrough

java
// Problem: Remove Duplicates from Sorted Array (in-place)
// Input: [1, 1, 2, 2, 3]
// Output: [1, 2, 3, _, _], return 3

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }

    int slow = 0;  // Points to last unique element

    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) {   // Found a new unique element!
            slow++;                       // Move slow forward
            nums[slow] = nums[fast];      // Write the new element
        }
    }

    return slow + 1;  // Length of unique portion
}

// Walkthrough: [1, 1, 2, 2, 3]
//
// slow=0, fast=1: nums[1]=1 == nums[0]=1 → skip
// slow=0, fast=2: nums[2]=2 != nums[0]=1 → slow=1, nums[1]=2 → [1,2,2,2,3]
// slow=1, fast=3: nums[3]=2 == nums[1]=2 → skip
// slow=1, fast=4: nums[4]=3 != nums[1]=2 → slow=2, nums[2]=3 → [1,2,3,2,3]
//
// Return slow+1 = 3 → first 3 elements [1,2,3] are the answer

Move Zeroes

Problem: Move all zeros to the end while maintaining order of non-zero elements.

java
public void moveZeroes(int[] nums) {
    int slow = 0;  // Where to place next non-zero

    // Fast pointer scans for non-zero elements
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {
            int temp = nums[slow];
            nums[slow] = nums[fast];
            nums[fast] = temp;
            slow++;
        }
    }
}

// [0, 1, 0, 3, 12]
// fast=0: nums[0]=0, skip
// fast=1: nums[1]=1≠0, swap(0,1) → [1, 0, 0, 3, 12], slow=1
// fast=2: nums[2]=0, skip
// fast=3: nums[3]=3≠0, swap(1,3) → [1, 3, 0, 0, 12], slow=2
// fast=4: nums[4]=12≠0, swap(2,4) → [1, 3, 12, 0, 0], slow=3

Problems

Pattern 3: Palindrome Check

What it is

A palindrome reads the same forwards and backwards. Use two pointers converging from both ends, comparing characters.

Step-by-Step

java
// "Is this string a palindrome?" (ignoring non-alphanumeric, case-insensitive)
public boolean isPalindrome(String s) {
    int left = 0;
    int right = s.length() - 1;

    while (left < right) {
        // Skip non-alphanumeric characters
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
            left++;
        }
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
            right--;
        }

        // Compare (case-insensitive)
        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
            return false;
        }

        left++;
        right--;
    }

    return true;
}

// "A man, a plan, a canal: Panama"
// After skipping non-alnum and lowering:
// 'a' vs 'a' ✓, 'm' vs 'm' ✓, 'a' vs 'a' ✓, ... all match → true

Valid Palindrome II (Can Remove One Character)

java
public boolean validPalindromeII(String s) {
    int left = 0;
    int right = s.length() - 1;

    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            // Try skipping left OR skipping right
            return isPalindromeRange(s, left + 1, right) || isPalindromeRange(s, left, right - 1);
        }
        left++;
        right--;
    }

    return true;
}

private boolean isPalindromeRange(String s, int left, int right) {
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

// "abca"
// left=0('a'), right=3('a'): match
// left=1('b'), right=2('c'): mismatch!
//   skip left: "ca" → palindrome? No
//   skip right: "bc" → palindrome? No... wait
//   skip left means check s[2:4] = "ca" → "ca" reversed = "ac" → No
//   skip right means check s[1:3] = "bc" → "bc" reversed = "cb" → No
//   Hmm, let me redo: skip 'b' → "aca" palindrome? Yes! → true

Problems

Pattern 4: Three Pointers / K-Sum Reduction

What it is

Reduce a K-sum problem to a (K-1)-sum problem by fixing one element, then use two pointers on the rest.

The Mental Model

3Sum = For each number, solve 2Sum on the remaining array.

Think of it like choosing a team captain (fix one person), then finding two teammates that balance the team (two-pointer search).

Step-by-Step Walkthrough

java
// Problem: Find all unique triplets [a, b, c] where a + b + c = 0
// Input: [-1, 0, 1, 2, -1, -4]

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);  // MUST sort first: [-4, -1, -1, 0, 1, 2]
    List<List<Integer>> result = new ArrayList<>();

    for (int i = 0; i < nums.length - 2; i++) {
        // Skip duplicates for the first number
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }

        // Fix nums[i], find two numbers that sum to -nums[i]
        int target = -nums[i];
        int left = i + 1;
        int right = nums.length - 1;

        while (left < right) {
            int twoSum = nums[left] + nums[right];

            if (twoSum == target) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                // Skip duplicates for second and third numbers
                while (left < right && nums[left] == nums[left + 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right - 1]) {
                    right--;
                }

                left++;
                right--;
            } else if (twoSum < target) {
                left++;
            } else {
                right--;
            }
        }
    }

    return result;
}

// Sorted: [-4, -1, -1, 0, 1, 2]
//
// i=0, nums[i]=-4, target=4:
//   left=1(-1), right=5(2): sum=1 < 4 → left++
//   left=2(-1), right=5(2): sum=1 < 4 → left++
//   left=3(0),  right=5(2): sum=2 < 4 → left++
//   left=4(1),  right=5(2): sum=3 < 4 → left++
//   left=5, left >= right → stop
//
// i=1, nums[i]=-1, target=1:
//   left=2(-1), right=5(2): sum=1 = 1 → Found! [-1,-1,2]
//   Skip dups, left=3, right=4
//   left=3(0), right=4(1): sum=1 = 1 → Found! [-1,0,1]
//
// i=2, nums[i]=-1, same as nums[1] → SKIP (avoid duplicate triplets)

Why We Skip Duplicates

Without skipping, [-1, -1, 0, 1] would produce [-1, 0, 1] twice (once using the first -1, once using the second). The if (i > 0 && nums[i] == nums[i-1]) continue; prevents this.

Extending to 4Sum

java
// 4Sum = fix one element + 3Sum on the rest
// 4Sum = fix two elements + 2Sum on the rest
// The pattern extends to any K-Sum

Problems

Pattern 5: Trapping Rain Water (Advanced)

What it is

Compute how much water can be trapped between bars after rainfall. This is a classic that combines two-pointer thinking with tracking maximums.

The Mental Model

For each position, the water level = min(max height to its left, max height to its right) - its own height. Water is limited by the shorter wall on either side.

        |
  |     |  |
  |  |  |  |  |
__|__|__|__|__|__
  3  1  2  4  1

At position 1 (height=1):
  max_left = 3, max_right = 4
  water = min(3, 4) - 1 = 2

Step-by-Step

java
public int trap(int[] height) {
    if (height.length == 0) {
        return 0;
    }

    int left = 0;
    int right = height.length - 1;
    int leftMax = height[left];
    int rightMax = height[right];
    int water = 0;

    while (left < right) {
        if (leftMax < rightMax) {
            // Left wall is the bottleneck
            left++;
            leftMax = Math.max(leftMax, height[left]);
            water += leftMax - height[left];  // Water above current bar
        } else {
            // Right wall is the bottleneck
            right--;
            rightMax = Math.max(rightMax, height[right]);
            water += rightMax - height[right];
        }
    }

    return water;
}

// Why does this work?
// We always process the side with the LOWER max.
// If leftMax < rightMax: we KNOW there's a wall on the right that's tall enough.
//   So the water at left position is determined by leftMax alone.
// This is the key insight — we don't need to know the exact rightMax,
//   just that it's >= leftMax.

Problems

Things You MUST Be Aware Of

1. Sorted Requirement

Two pointers (converging) requires SORTED input.
If the input isn't sorted, either:
  - Sort it first (O(n log n)) — if original indices don't matter
  - Use a hash map instead — if you need original indices

2. Duplicate Handling in 3Sum

The #1 bug in 3Sum: forgetting to skip duplicates.
You need to skip at THREE levels:
  - The outer loop (first number)
  - After finding a match (second number)
  - After finding a match (third number)

3. Off-by-One Errors

java
// Common mistake: wrong loop condition
while (left < right)   // Correct for most cases (don't process same element twice)
while (left <= right)  // Only when left and right can be the same valid position

4. When NOT to Use Two Pointers

- Unsorted array + need original indices → use hash map
- Not looking for pairs/triplets → probably wrong technique
- Elements can be used multiple times → might need different approach

Decision Guide

Need pairs summing to target?
  ├── Array sorted? → Converging two pointers
  └── Not sorted?
       ├── Need indices? → Hash map (Two Sum pattern)
       └── Need values?  → Sort first, then two pointers

Remove/partition in-place?
  └── Fast & slow pointers

Palindrome?
  └── Converge from both ends

Triplets/quadruplets?
  └── Fix K-2 elements, two-pointer on the rest

Container / trapping water?
  └── Converging + tracking max from both sides