sko.kr

Algorithms - 3. Two Pointers

algorithmstwo-pointersarraysstringsoptimization
By sko•9/28/2025•9 min read

When to use Two Pointers

Use Two Pointers when you need to systematically explore relationships between elements at different positions. The technique works whenever you can make progress by moving pointers based on some condition, eliminating possibilities as you go.

Problems requiring sorted arrays

  • Two Sum with target (classic use case - needs sorting to know which pointer to move)
  • Three Sum / Four Sum (with nested pointer pairs - requires ordering for elimination)
  • Finding pairs with specific difference (needs ordering to eliminate regions)

Problems that work on unsorted arrays

  • Container with Most Water (indices provide the ordering, not values)
  • Palindrome validation (natural ordering from both ends)
  • Reversing arrays/strings (swap from both ends)
  • Partitioning problems (Dutch National Flag, Quick Sort partition)
  • Fast/slow pointer variants (cycle detection, finding middle element)
  • Remove duplicates with read/write pointers (maintain invariants as you scan)

Example problem (Sorted Array)

Finding a Pair with Target Sum: Given a sorted array of integers [1, 3, 4, 6, 8, 9, 11] and target sum 14, find two numbers that add up to the target.

  • Start with pointers at positions 0 and 6: 1 + 11 = 12 (too small)
  • Move left pointer to position 1: 3 + 11 = 14 (found!)
  • Answer: Elements at indices [1, 6] which are 3 and 11

Without sorting, you'd need O(n²) comparisons. With Two Pointers on a sorted array, you find it in O(n) time.

Example problem (Unsorted Array)

Container with Most Water: Given heights [1, 8, 6, 2, 5, 4, 8, 3, 7], find two lines that together with the x-axis form a container holding the most water.

  • Start with pointers at positions 0 and 8: area = 8 × min(1, 7) = 8
  • Move left pointer (smaller height) to position 1: area = 7 × min(8, 7) = 49
  • Continue until pointers meet, tracking maximum area
  • Answer: Indices [1, 8] with area 49

No sorting needed! The indices themselves provide the width, and we move the pointer with smaller height to potentially find a larger area.

Single most important insight

Two pointers systematically explores the solution space by eliminating impossible options with each pointer movement - whether through sorted order (for sum problems) or positional constraints (for geometric problems), each comparison gives us knowledge about many possibilities, not just one.

Mental note: Unlike Kadane's and Sliding Window which focus on "best subarray ending at position i", Two Pointers focuses on relationships between elements at different positions. You're not anchored to any position - instead, you're exploring pairs/relationships by moving two independent pointers based on comparisons. While Kadane's asks "extend or restart at this position?", Two Pointers asks "which pointer should move to find a better relationship?"

Mental Model Comparison

  • Kadane's Algorithm: "What's the best subarray ending at position i?" - anchored to endpoints
  • Sliding Window: "What's the best window ending at position i?" - anchored to right boundary
  • Two Pointers: "What relationship between two positions should we explore next?" - no anchor, pure exploration

The lack of positional anchoring is what makes Two Pointers unique - you're free to move either pointer based on the comparison, systematically eliminating entire regions of the solution space.

Decision Framework

For sorted array problems (Two Sum)

  • Sum too large? Move right pointer left (decrease sum)
  • Sum too small? Move left pointer right (increase sum)
  • Sum equals target? Found the pair!

For unsorted array problems (Container with Most Water)

  • Move the pointer pointing to the smaller height
  • Why? The smaller height limits the area, so we look for a potentially taller line
  • Track the maximum area seen so far

Code Examples

Sorted Array: Two Sum

function twoSum(nums: number[], target: number): [number, number] | null {
  let left = 0;
  let right = nums.length - 1;

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

    // DECISION FRAMEWORK
    if (currentSum > target) {
      // Sum too large: decrease by moving right pointer left
      right--;
    } else if (currentSum < target) {
      // Sum too small: increase by moving left pointer right
      left++;
    } else {
      // Found the target sum
      return [left, right];
    }
  }

  return null; // No valid pair found
}

// Example usage with data from the problem
const sortedArray = [1, 3, 4, 6, 8, 9, 11];
const targetSum = 14;
const result = twoSum(sortedArray, targetSum);
console.log(result); // [1, 6] - indices of 3 and 11

Unsorted Array: Container with Most Water

function maxArea(heights: number[]): number {
  let left = 0;
  let right = heights.length - 1;
  let maxWater = 0;

  while (left < right) {
    const width = right - left;
    const minHeight = Math.min(heights[left], heights[right]);
    const currentWater = width * minHeight;

    maxWater = Math.max(maxWater, currentWater);

    // DECISION FRAMEWORK
    if (heights[left] < heights[right]) {
      // Left wall is limiting factor, try to find taller left wall
      left++;
    } else {
      // Right wall is limiting factor, try to find taller right wall
      right--;
    }
  }

  return maxWater;
}

// Example usage with unsorted array from the problem
const heights = [1, 8, 6, 2, 5, 4, 8, 3, 7];
console.log(maxArea(heights)); // 49 (between indices 1 and 8)

Unsorted Array: Palindrome Check

function isPalindrome(s: string): boolean {
  let left = 0;
  let right = s.length - 1;

  while (left < right) {
    // DECISION FRAMEWORK
    if (s[left] !== s[right]) {
      return false; // Mismatch found
    }
    left++;
    right--;
  }

  return true; // All characters matched
}

// Works on any string - no sorting needed!
console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("hello")); // false

Beyond Sorted Arrays: When Two Pointers Still Works

Common misconception: "Two pointers only works on sorted arrays."

This is false! Two pointers works whenever you can:

  1. Make systematic progress by moving pointers based on a condition
  2. Eliminate possibilities or explore the solution space methodically
  3. Avoid redundant comparisons by using some structure (not necessarily sorted order)

Why Container with Most Water works on unsorted arrays

The key insight: The indices themselves provide the ordering we need!

  • Width is always right - left (decreases as pointers converge)
  • We move the pointer with smaller height because it's the limiting factor
  • Each move explores containers with smaller width but potentially greater height
  • No need to sort because position (not value) determines the width

Different structures enable Two Pointers

  1. Sorted values → Enables directional decisions for sum/difference problems
  2. Positional indices → Provides natural ordering for geometric problems
  3. String/array ends → Natural boundaries for palindrome/reversal problems
  4. Invariant maintenance → Read/write pointers for in-place modifications

The "structure" doesn't have to be sorted values - it just needs to enable systematic exploration!

Doubt buster (Sorted Array Case)

Common doubt: "The algorithm moves pointers based on comparison with the target, but what if we skip over the correct pair? Once we move past an element, we never go back - couldn't this miss the solution?"

Why this thinking is wrong

Key realization: Every pointer movement eliminates an entire class of impossible pairs!

  • When sum < target → move left pointer right → eliminates ALL pairs with current left element (they're all too small)
  • When sum > target → move right pointer left → eliminates ALL pairs with current right element (they're all too large)

The systematic exploration in action

Let's trace [1, 3, 4, 6, 8] with target 7:

Step 1: left=0 (1), right=4 (8) → sum=9 > 7
        Eliminate: All pairs with 8 and elements ≥1
        Move right to 3

Step 2: left=0 (1), right=3 (6) → sum=7 = 7  → FOUND!

Notice what happened at Step 1:

  • We compared 1+8=9 with target 7
  • Since 9 > 7, we know that 8 paired with 1, 3, 4, or 6 will ALL be ≥ 9
  • So we safely eliminate 8 from consideration entirely

Why directional movement guarantees completeness

The algorithm maintains this invariant:

  • All pairs with left elements we've passed are fully explored
  • All pairs with right elements we've passed are fully explored
  • The remaining unexplored space shrinks systematically until empty

The guarantee: Because sorted order lets us know which entire regions are impossible based on a single comparison, we can eliminate many pairs with each pointer movement. This systematic exploration ensures we check every viable pair exactly once while skipping all the impossible ones!

The magic is in the sorted array: it transforms a comparison with one pair into knowledge about many pairs, letting us explore the entire solution space in O(n) time instead of O(n²).

Doubt buster (Unsorted Array Case)

Common doubt: "How can two pointers work on unsorted arrays? Don't we need sorting to know which pointer to move?"

Why this thinking is wrong

Key realization: Sorting is just ONE way to create structure. Two pointers works whenever there's ANY exploitable structure!

For unsorted arrays, the structure comes from:

  • Positional relationships (Container with Most Water: indices determine width)
  • Natural boundaries (Palindrome: comparing from ends inward)
  • Maintained invariants (Partitioning: elements before pointer satisfy a condition)

Container with Most Water - Why no sorting needed

Consider heights [1, 8, 6, 2, 5, 4, 8, 3, 7]. The algorithm works because:

  1. Width is determined by indices, not values: Distance between positions i and j is always |i - j|
  2. Moving pointers always decreases width: This is guaranteed by index positions
  3. We move the shorter line hoping for a taller one: Since width decreases, only a taller line could give more area

The crucial insight: The indices themselves provide the ordering we need. We're not comparing values to find pairs - we're using positional relationships that exist regardless of value order.

Why sorting would actually break some problems

For Container with Most Water, sorting would destroy the positional relationships:

  • Original: [1, 8, 6, 2, 5, 4, 8, 3, 7] - indices matter
  • Sorted: [1, 2, 3, 4, 5, 6, 7, 8, 8] - lost original positions!

The problem relies on the original positions of elements, not their sorted order.

Remember: Two pointers needs structure, not necessarily sorted values. Identify what structure enables systematic exploration in your specific problem.

Variations and Patterns

Fast and Slow Pointers (Tortoise and Hare)

A special variant where pointers move at different speeds:

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next; // Move 1 step
    fast = fast.next.next; // Move 2 steps

    // DECISION FRAMEWORK
    if (slow === fast) {
      return true; // Cycle detected
    }
  }

  return false; // No cycle
}

Read/Write Pointers for In-Place Modifications

This pattern uses two pointers moving in the same direction at different speeds to modify an array in-place:

function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0;

  let writePointer = 0; // Where to write next unique element

  for (let readPointer = 1; readPointer < nums.length; readPointer++) {
    // DECISION FRAMEWORK
    if (nums[readPointer] !== nums[writePointer]) {
      writePointer++;
      nums[writePointer] = nums[readPointer];
    }
  }

  return writePointer + 1; // Length of unique elements
}

// Example: [1,1,2,2,3] becomes [1,2,3,2,3] with length 3

How it works:

  • Read pointer scans through the entire array looking for new unique values
  • Write pointer marks where the next unique value should be written
  • When read pointer finds a value different from the value at write pointer:
    1. Move write pointer forward
    2. Copy the new unique value to the write position
  • The array is modified in-place: [1,1,2,2,3] → [1,2,3,2,3]
    • First 3 elements are now the unique values: [1,2,3]
    • Remaining elements [2,3] are ignored (they're beyond our new length)
  • Returns 3, indicating the first 3 elements contain all unique values

This pattern is powerful for in-place array modifications where you want to keep certain elements while removing others, all in O(n) time with O(1) space.

← Back to Blog