Two Pointer Technique

The Two Pointer technique is an essential pattern where two pointers iterate through the data structure in tandem. This is often used to search for pairs in a sorted array or to reverse operations.

1. Types of Two Pointers

1. Opposite Direction: One pointer starts at the beginning (left) and the other at the end (right). They move toward each other.
   • Usage: Two Sum (Sorted), Valid Palindrome, Container With Most Water.
2. Same Direction (Fast & Slow): Both pointers start at the beginning, but one moves faster than the other.
   • Usage: Cycle Detection, Remove Duplicates, Finding the Middle of a Linked List.

---

2. The Mathematical Anchor: Proof of Convergence

Why does moving pointers toward each other find a solution like Two Sum on a sorted array?

The Convergence Proof (Proof by Contradiction)

Assume we have a sorted array and are looking for target. Pointers are L and R.

1. If arr[L] + arr[R] > target, we decrement R.
2. Why don’t we miss a potential solution by moving R?
3. Reason: Since the array is sorted, arr[L] + any element after R would be even larger than arr[L] + arr[R]. Therefore, no solution involving the current R can exist with any L' ≥ L. By decrementing R, we safely discard a search space that cannot contain the target.

By repeatedly narrowing the search space based on the sorted property, the algorithm is guaranteed to either find the target or correctly conclude it doesn’t exist.

---

3. Interactive Visualizer: Container With Most Water

This visualizer demonstrates the Opposite Direction two-pointer approach to solve the “Container With Most Water” problem. The goal is to find two lines that form a container holding the maximum water. We start with the widest container and move the shorter line inward to try and find a taller line that compensates for the reduced width.

Speed:

Press Start to begin...

Max Area: 0

Current Area: 0

4. Problem 1: Container With Most Water

Difficulty: Medium

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i-th line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water.

Example:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The max area is between index 1 (height 8) and index 8 (height 7).
Area = min(8, 7) * (8 - 1) = 7 * 7 = 49.

Solution Walkthrough

Using the Two Pointer technique:

1. Initialize left at 0 and right at n-1.
2. Calculate the area formed by lines at left and right.
3. Update maximum area.
4. Move the pointer pointing to the shorter line inward. (Why? Because moving the taller line inward can only reduce width without guaranteeing a height increase that compensates, as the area is limited by the shorter line).

View Java Solution

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

    while (left < right) {
      int currentArea = Math.min(height[left], height[right]) * (right - left);
      maxArea = Math.max(maxArea, currentArea);

      if (height[left] < height[right]) {
        left++;
      } else {
        right--;
      }
    }
    return maxArea;
  }
}

View Go Solution

package main

func maxArea(height []int) int {
	maxArea := 0
	left := 0
	right := len(height) - 1

	for left < right {
		h := min(height[left], height[right])
		w := right - left
		area := h * w

		if area > maxArea {
			maxArea = area
		}

		if height[left] < height[right] {
			left++
		} else {
			right--
		}
	}

	return maxArea
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

---

5. Problem 2: Squares of a Sorted Array

Difficulty: Easy

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Example:

Input: nums = [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Solution Walkthrough

Since the array contains negative numbers, the squares might not be sorted (e.g., -4 becomes 16). The largest squares will be at the extremes (very negative or very positive).

1. Initialize left = 0, right = n-1.
2. Fill the result array from the end (index = n-1 down to 0).
3. Compare abs(nums[left]) and abs(nums[right]) (or their squares).
4. Place the larger square at the current result index and move the corresponding pointer inward.

View Java Solution

class Solution {
  public int[] sortedSquares(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    int left = 0;
    int right = n - 1;

    for (int i = n - 1; i >= 0; i--) {
      int squareLeft = nums[left] * nums[left];
      int squareRight = nums[right] * nums[right];

      if (squareLeft > squareRight) {
        result[i] = squareLeft;
        left++;
      } else {
        result[i] = squareRight;
        right--;
      }
    }

    return result;
  }
}

View Go Solution

package main

func sortedSquares(nums []int) []int {
	n := len(nums)
	result := make([]int, n)
	left := 0
	right := n - 1

	for i := n - 1; i >= 0; i-- {
		squareLeft := nums[left] * nums[left]
		squareRight := nums[right] * nums[right]

		if squareLeft > squareRight {
			result[i] = squareLeft
			left++
		} else {
			result[i] = squareRight
			right--
		}
	}

	return result
}

---

6. Deep Dive Strategy Lab: Two Pointer Technique

Intuition Through Analogy

Think of this chapter like organizing items on a warehouse shelf. The goal is not to memorize a fixed trick, but to repeatedly answer:

1. What is the bottleneck?
2. Which constraint dominates (time, memory, latency, correctness)?
3. Which representation makes the bottleneck easier to eliminate?