Two Pointers

Two pointers is a fundamental technique that uses two references to traverse data structures simultaneously. There are two primary variants:

Collision Pointers (Converging Pointers): Both pointers start from opposite ends and move toward each other.

Fast and Slow Pointers: Both pointers move in the same direction but at different speeds. This approach is particularly useful for cycle detection in linked lists and certain array problems.

Collision Pointers Example

Problem: Container With Most Water (LeetCode 11)

Given an array of heights, find two lines that together with the x-axis form a container holding the maximum amount of water.

Approach: Initialize pointers at both ends. The container width equals the distance between pointers, and the height equals the minimum of the two boundary heights. To optimize, always move the pointer pointing to the shorter line—this ensures we don't miss potentially larger containers.

Proof of Correctness: When the left height is less than the right height, moving the right pointer leftward cannot increase the container volume because the height is constrained by the shorter left boundary. The width only decreases while height remains unchanged or decreases. Therefore, only moving the left pointer can potentially find a larger container.

int maxArea(vector<int>& height) {
    int left = 0, right = height.size() - 1, result = 0;
    while (left < right) {
        int area = min(height[left], height[right]) * (right - left);
        result = max(result, area);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return result;
}

Related Problem: 3Sum (LeetCode 15)

Fast and Slow Pointers Example

Problem: Happy Number (LeetCode 202)

Determine if a number is "happy"—repeatedly replacing it with the sum of squares of its digits eventually reaches 1.

Analysis: For non-happy numbers, the process enters a cycle that never reaches 1. The maximum input is 2^31 - 1 (10 digits). The maximum sum of squares for any number under this limit is 10 × 9² = 810. Therefore, all subsequent calculations fall with in the range [1, 810].

Using Floyd's cycle detection algorithm, if a cycle exists, the two pointers will eventually meet. If the meeting point is 1, the number is happy.

int digitSquareSum(int n) {
    int sum = 0;
    while (n > 0) {
        int digit = n % 10;
        sum += digit * digit;
        n /= 10;
    }
    return sum;
}

bool isHappy(int n) {
    int slow = n;
    int fast = digitSquareSum(n);
    while (slow != fast) {
        slow = digitSquareSum(slow);
        fast = digitSquareSum(digitSquareSum(fast));
    }
    return slow == 1;
}

Sliding Window

The sliding window technique maintains a contiguous subarray or substring as window boundaries expand and contract. Unlike two pointers, which typically traverse the entire array, sliding windows work with variable-length bounded intervals.

Sliding Window Example

Problem: Fruit Into Baskets (LeetCode 904)

Find the maximum total fruits that can be collected given that you can only hold two types of fruits in your basket.

Strategy:

1. Use a hash map to track the count of each fruit type currently in the window
2. Expand the right boundary until three distinct fruit types are ancountered
3. Shrink the left boundary until only two fruit types remain
4. Update the maximum window size at each valid state

int totalFruit(vector<int>& fruits) {
    unordered_map<int, int> fruitCount;
    int maxLength = 0;
    int n = fruits.size();
    
    for (int left = 0, right = 0; right < n; right++) {
        fruitCount[fruits[right]]++;
        
        while (fruitCount.size() > 2) {
            fruitCount[fruits[left]]--;
            if (fruitCount[fruits[left]] == 0) {
                fruitCount.erase(fruits[left]);
            }
            left++;
        }
        
        maxLength = max(maxLength, right - left + 1);
    }
    return maxLength;
}

Related Problem: Max Consecutive Ones III (LeetCode 1004)