Two Pointers

What you'll learn

• The Golden Rule: When to Use Two Pointers

  Reach for two pointers when you see any of these signals: | Signal | Example | |--------|---------| | Sorted array or linked list | Find a pair that sums to a target | | Find pair/triplet satisfying a condition | Three values that sum to…

• Three Variants of Two Pointers

• Variant 1: Opposite Ends (Converging Pointers)

  Two pointers start at opposite ends and move toward each other. Used when you need to find pairs or evaluate conditions by comparing elements from both extremes. Use cases: Pair sum in sorted array, container with most water, trapping ra…

• Variant 2: Same Direction (Slow/Fast or Read/Write)

  Both pointers move in the same direction but at different speeds or with different roles. One pointer reads values while the other marks the write position. Use cases: Remove duplicates, move zeros, partition arrays, linked list cycle de…

• Variant 3: Two Arrays

  One pointer per array, advancing based on comparisons between elements at each pointer. Use cases: Merge sorted arrays, find intersection, find median of two sorted arrays. ---

• Pattern: Pair with Target Sum (Sorted Array)

  Problem: Given a sorted array, find two numbers that add up to a target sum.

• The Key Insight

  In a sorted array, if the current pair sum is: - Too small -- move the left pointer right (increases the sum) - Too large -- move the right pointer left (decreases the sum) - Equal to target -- found the pair This works because sorted or…

• Why This Eliminates Possibilities Correctly

  When arr[L] + arr[R] Time: O(n) -- each pointer moves at most n times Space: O(1) -- only two variables ---

• Pattern: Three Sum (Sort + Two Pointers)

  Problem: Find all unique triplets in an array that sum to zero.

• Strategy

  1. Sort the array 2. For each element arr[i], use two pointers on the remaining subarray arr[i+1..n-1] to find pairs that sum to -arr[i] 3. Skip duplicates at every level to avoid repeated triplets

• Duplicate Handling

  Duplicates must be skipped at two levels: - Outer loop: If arr[i] == arr[i-1], skip (same fixed element would produce same triplets) - Inner loop: After finding a valid triplet, advance both pointers past duplicates Time: O(n^2) -- sorti…

• Pattern: Container With Most Water

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

• Why Moving the Shorter Side is Always Correct

  The water held is min(height[L], height[R]) (R - L). When we move any pointer inward, the width (R - L) decreases by 1. The only way to potentially find a larger area is to find a taller minimum height. Key proof intuition: If height[L]…

• Pattern: Remove Duplicates In-Place

  Problem: Given a sorted array, remove duplicates in-place and return the new length.

• Slow/Fast Pointer Strategy

  - Slow pointer (write position): marks where the next unique element should be placed - Fast pointer (reader): scans through every element When the fast pointer finds a value different from the value at the slow pointer, we advance slow…

• Implementation

  Time: O(n) Space: O(1) ---

• Pattern: Dutch National Flag (Three-Way Partition)

  Problem: Sort an array containing only 0s, 1s, and 2s in a single pass.

• Three Pointers: Low, Mid, High

  This uses three pointers to partition the array into four regions:

• Algorithm

  - If arr[mid] == 0: swap with arr[low], advance both low and mid - If arr[mid] == 1: just advance mid (it is in the right place) - If arr[mid] == 2: swap with arr[high], decrement high (do NOT advance mid, since the swapped value is unex…

• ASCII Trace

• Implementation

  Time: O(n) -- single pass Space: O(1) ---

• Pattern: Trapping Rain Water

  Problem: Given elevation heights, compute how much water can be trapped between bars.

• Two-Pointer Approach

  The water at any position depends on: min(maxleft, maxright) - height[i] Instead of precomputing leftmax and rightmax arrays, we can use two pointers: - Maintain leftmax (maximum height seen from left) and rightmax (from right) - Process…

• Why This Works

  If leftmax Time: O(n) Space: O(1) -- better than the O(n) prefix array approach

• Comparison: Two Pointers vs Stack Approach

  | Approach | Time | Space | When to prefer | |----------|------|-------|----------------| | Two pointers | O(n) | O(1) | When you want optimal space | | Monotonic stack | O(n) | O(n) | When computing water layer by layer (horizontal) | |…

• Pattern: Squares of a Sorted Array

  Problem: Given a sorted array (may contain negatives), return an array of squares in sorted order.

• Handling Negatives

  A sorted array like [-4, -2, -1, 0, 3, 5] has the largest squares at the extremes (leftmost negative or rightmost positive). Use converging pointers to build the result from largest to smallest.

• Implementation

  Time: O(n) Space: O(n) for the result array

• Alternative: Partition-Point Based Approach

  Another way to think about this: find the partition point where negatives end and positives begin. Then use two pointers moving outward from that partition: Both approaches are O(n). The converging-from-ends approach is more concise; the…

• Comparison: Two Pointers vs Sliding Window

  These patterns are related but distinct: | Criterion | Two Pointers | Sliding Window | |-----------|-------------|----------------| | Pointer movement | Independent (converge or diverge) | Together (window expands/shrinks) | | What they…

• Decision Guide

  - "Find two numbers that..." -> Two pointers (converging) - "Longest subarray where..." -> Sliding window - "Remove/partition in-place" -> Two pointers (same direction) - "Maximum sum of subarray of size k" -> Sliding window (fixed) - "C…

• Complexity Summary

  | Pattern | Time | Space | Notes | |---------|------|-------|-------| | Pair sum (sorted) | O(n) | O(1) | Single pass with converging pointers | | Three sum | O(n^2) | O(1) | Sort + for-each + two pointers | | Container with most water |…

• General Complexity Rules

  - Converging pointers on one array: O(n) time, O(1) space - Fixed element + two pointers: O(n^2) time (one outer loop) - Two separate arrays: O(n + m) time - Sorting prerequisite adds: O(n log n) but is dominated by O(n^2) when present ---

• Common Mistakes and Edge Cases

  1. Forgetting to handle duplicates in three-sum (produces repeated triplets) 2. Not advancing mid after a swap with low in Dutch National Flag is fine, but advancing mid after swap with high is the real bug 3. Using two pointers on unsor…

• Practice Problems (By Difficulty)

• Easy

  - Pair with target sum in sorted array - Remove duplicates from sorted array - Squares of a sorted array - Move all zeros to end

• Medium

  - Three sum (find all unique triplets summing to zero) - Container with most water - Sort an array of 0s, 1s, and 2s (Dutch National Flag) - Trapping rain water

• Hard

  - Four sum (extend three-sum pattern) - Minimum window containing elements from two arrays - Trapping rain water II (2D version -- different technique needed)