Chapter 1: Two Pointers

Interview Frequency: ⬛⬛⬛⬛⬛ (5/5) — Appears in ~20% of coding interviews

Prerequisites: None (start here)

The Signal

How do you know a problem is calling for the Two Pointers technique? Look for these clues in the problem statement:

• The input array or string is sorted, or the problem asks you to sort it first.
• You need to find a pair (or triplet, or group) of elements satisfying some condition (sum, difference, comparison).
• The problem asks you to do something in-place with O(1) extra space, such as removing duplicates or partitioning.
• You are comparing elements from both ends of a sequence — for example, checking if a string is a palindrome.
• A brute-force approach would require nested loops (O(n^2)), and you suspect there is a way to reduce it to O(n).

If you spot two or more of these signals, the Two Pointers pattern should be at the top of your mind.

When NOT to Use

• Finding ALL pairs in an unsorted array (e.g., "count all pairs with difference K"). Two pointers requires sorted data to eliminate candidates. If you need all pairs regardless of order and sorting would lose index information, use a hash map to look up complements in O(n). Example: Two Sum (LeetCode 1) on an unsorted array where you need original indices.
• Finding subarrays rather than pairs. If the problem asks for a contiguous subarray with a given sum or property (e.g., "longest subarray with sum <= K"), you need sliding window or prefix sum, not two pointers. Two pointers finds pairs of elements, not contiguous ranges.
• When elements must be a specific distance apart. Problems like "find the maximum sum of two elements at least K positions apart" require a sliding window or deque-based approach, not two pointers converging from both ends.
• When the array is unsorted and sorting would lose required information. If you need to return original indices (not values) and the problem does not provide a sorted array, sorting destroys that information. Use a hash map instead. Example: the original Two Sum problem needs index pairs from the unsorted array.
• When you need the kth smallest pair distance across all pairs. Even though this involves pairs, the search space is over distances, not the array itself. Use binary search on the answer combined with a two-pointer count. Applying raw two pointers to enumerate pairs would be O(n^2).
• When the problem involves non-comparable elements or complex constraints. If the decision of which pointer to move depends on more than a simple less-than/greater-than comparison (e.g., matching parentheses, frequency constraints), two pointers lacks a clear elimination argument. Consider stack, hash map, or sliding window instead.

The Mental Model

The core insight: in a sorted array, two pointers moving inward from opposite ends systematically explore all meaningful pairs in linear time because the sorted order lets you decide which pointer to move at each step.

Visual Walkthrough

Problem: Two Sum II — Given a sorted array [2, 7, 11, 15] and target 9, find two numbers that add up to the target. Return their 1-indexed positions.

Frame 1: Initialization

Array:  [ 2,  7, 11, 15 ]
Index:    0   1   2   3

          L               R
          |               |
          v               v
        [ 2,  7, 11, 15 ]

left  = 0  (pointing at 2)
right = 3  (pointing at 15)
sum   = 2 + 15 = 17

Thought: 17 > 9. The sum is too large. Since the array is sorted, the only way to make the sum smaller is to move the right pointer left. Moving left pointer right would make the sum even larger.

Frame 2: Move right pointer left

          L           R
          |           |
          v           v
        [ 2,  7, 11, 15 ]

left  = 0  (pointing at 2)
right = 2  (pointing at 11)
sum   = 2 + 11 = 13

Thought: 13 > 9. Still too large. Move right pointer left again.

Frame 3: Move right pointer left again

          L       R
          |       |
          v       v
        [ 2,  7, 11, 15 ]

left  = 0  (pointing at 2)
right = 1  (pointing at 7)
sum   = 2 + 7 = 9

Thought: 9 == 9. Found it! The answer is indices (0+1, 1+1) = (1, 2) in 1-indexed terms.

The Elimination Visualized

Think of all possible pairs as a matrix. Each step eliminates an entire row or column:

        2    7   11   15
   2  [ 4    9   13   17 ]  <-- right=3: sum=17 > 9, eliminate column 15
   7  [ 9   14   18   22 ]
  11  [13   18   22   26 ]
  15  [17   22   26   30 ]

        2    7   11
   2  [ 4    9   13 ]  <-- right=2: sum=13 > 9, eliminate column 11
   7  [ 9   14   18 ]
  11  [13   18   22 ]
  15  [17   22   26 ]

        2    7
   2  [ 4    9 ]  <-- right=1: sum=9 == target. FOUND!
   7  [ 9   14 ]
  11  [13   18 ]
  15  [17   22 ]

Each pointer move eliminates one row or column of this matrix, which is why the algorithm is O(n) instead of O(n^2).

Diagonal entries (self-pairs like 2+2) are excluded since two-pointer uses distinct indices. The matrix shows why opposite-direction scanning eliminates pairs efficiently.

The Template

def two_pointer_pair(arr, target):
    """
    Generic two-pointer template for sorted arrays.
    Finds a pair that satisfies some condition.
    """
    left = 0
    right = len(arr) - 1            # WHY: Start at extremes to cover full search space

    while left < right:              # WHY: < not <= because same element can't pair with itself
        current = arr[left] + arr[right]  # or whatever combination

        if current == target:
            return (left, right)  # found the answer
        elif current < target:
            left += 1             # WHY: Sorted — only way to increase sum is move left forward
        else:
            right -= 1            # WHY: Sorted — only way to decrease sum is move right back

    return None  # no valid pair found

Variant — Same-direction two pointers (fast/slow):

def remove_duplicates(arr):
    """
    Two pointers moving in the same direction.
    'slow' marks the write position; 'fast' scans ahead.
    """
    if not arr:
        return 0

    slow = 0
    for fast in range(1, len(arr)):
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]

    return slow + 1  # length of deduplicated portion

Complexity

Why O(n)? Each pointer moves in only one direction and each moves at most n steps. The total number of steps across both pointers is at most 2n, which is O(n).

Practice Problems

Easy: Valid Palindrome (LeetCode 125)

Trap: Must strip non-alphanumeric chars and normalize case before comparing — easy to forget one

Problem Statement: Given a string s, determine if it is a palindrome considering only alphanumeric characters and ignoring cases. For example, "A man, a plan, a canal: Panama" is a palindrome. An empty string is considered a valid palindrome.

Hints:

1. You need to compare characters from opposite ends. What pattern does that suggest?
2. You will need to skip non-alphanumeric characters. How do you handle that with two pointers?
3. Use left and right pointers. Advance left past non-alphanumeric characters; retreat right past them. Then compare s[left].lower() with s[right].lower().

Solution Approach:

Place one pointer at the beginning and one at the end. The key complication is that you must skip over non-alphanumeric characters. At each step, advance the left pointer forward until it sits on an alphanumeric character, and move the right pointer backward until it also sits on one. Then compare the two characters (case-insensitively). If they do not match, return False immediately. If they match, move both pointers inward and repeat.

This works because a palindrome reads the same forwards and backwards. By converging from both ends, you verify this property character by character. Skipping non-alphanumeric characters is just bookkeeping — it does not change the fundamental two-pointer logic.

The time complexity is O(n) since each pointer traverses the string at most once. Space complexity is O(1) since you only use two index variables.

Code Solution:

def is_palindrome(s: str) -> bool:
    left = 0
    right = len(s) - 1

    while left < right:
        # Skip non-alphanumeric from the left
        while left < right and not s[left].isalnum():
            left += 1
        # Skip non-alphanumeric from the right
        while left < right and not s[right].isalnum():
            right -= 1

        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True

Medium: 3Sum (LeetCode 15)

Trap: Must skip duplicate values after finding a match, or you'll get duplicate triplets in the output

Problem Statement: Given an integer array nums, find all unique triplets [nums[i], nums[j], nums[k]] such that i != j != k and nums[i] + nums[j] + nums[k] == 0. The solution set must not contain duplicate triplets.

Hints:

1. If you fix one element, the remaining problem is "find two numbers that sum to a specific target" — which is exactly Two Sum II on a sorted array.
2. Sort the array first. Then for each element nums[i], use two pointers on the subarray to the right of i to find pairs that sum to -nums[i].
3. To avoid duplicates, skip over repeated values for i, and also skip repeated values when moving the left and right pointers after finding a valid triplet.

Solution Approach:

Sort the array. Then iterate through each index i from 0 to n-3. For each i, set left = i + 1 and right = n - 1, and look for pairs where nums[left] + nums[right] == -nums[i]. This reduces the problem to running Two Sum II for each fixed element.

The tricky part is avoiding duplicate triplets. After sorting, duplicate values are adjacent. So if nums[i] == nums[i-1], skip i because you already processed that value. Similarly, after finding a valid triplet, advance left past duplicates and retreat right past duplicates before continuing.

The outer loop runs O(n) times, and for each iteration the two-pointer scan takes O(n), giving O(n^2) total. Sorting costs O(n log n), which is dominated. Space is O(1) extra beyond the output.

Code Solution:

def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []

    for i in range(len(nums) - 2):
        # Skip duplicate values for the first element
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        target = -nums[i]
        left = i + 1
        right = len(nums) - 1

        while left < right:
            current_sum = nums[left] + nums[right]

            if current_sum == target:
                result.append([nums[i], nums[left], nums[right]])
                # Skip duplicates for left and right
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif current_sum < target:
                left += 1
            else:
                right -= 1

    return result

Hard: Trapping Rain Water (LeetCode 42)

Trap: Using a stack-based approach when two pointers is simpler and O(1) space — and miscalculating water by using height[i] instead of min(left_max, right_max) - height[i]

Problem Statement: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. (LeetCode 42)

Example: height = [0,1,0,2,1,0,1,3,2,1,2,1] → 6

Hints:

1. Water above bar i equals min(max_height_to_left, max_height_to_right) - height[i] (if positive). The water is bounded by the shorter of the two tallest walls on either side.
2. You can compute left-max and right-max arrays in two passes (O(n) space), but two pointers achieves O(1) space.
3. Two-pointer approach: maintain left_max and right_max as you advance inward. Process from the side with the smaller max — that side's water is fully determined.

Solution Approach:

Start with left = 0, right = n-1, left_max = 0, right_max = 0. At each step, process the side with the smaller max. If left_max <= right_max, the water at left is left_max - height[left] (the right boundary is guaranteed to be at least right_max, which is >= left_max). Otherwise, process from the right side. This ensures we always know the constraining wall height.

Code Solution:

def trap(height: list[int]) -> int:
    if not height:
        return 0

    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0

    while left < right:
        if height[left] <= height[right]:
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1

    return water

Complexity: O(n) time, O(1) space. Each pointer moves at most n times.

Medium: Container With Most Water (LeetCode 11)

Trap: Always move the shorter line's pointer — moving the taller one can never improve the area

Problem Statement: Given n non-negative integers height[0], height[1], ..., height[n-1] where each represents a point at coordinate (i, height[i]), find two lines that together with the x-axis form a container that holds the most water. Return the maximum amount of water the container can store. (You may not slant the container.)

Hints:

1. The area between two lines at indices i and j is min(height[i], height[j]) * (j - i). You want to maximize this.
2. Start with the widest container (pointers at both ends). The width can only decrease, so to get more area you need to increase the height.
3. Always move the pointer pointing to the shorter line inward. Why? Because moving the taller line inward can never increase the area — the height is constrained by the shorter line, and the width decreases.

Solution Approach:

Start with left = 0 and right = n - 1. Calculate the area. Then move the pointer that points to the shorter line, because the water height is limited by the shorter of the two lines. If you moved the pointer at the taller line instead, the width would shrink and the height could not increase (it is still limited by the shorter line), so the area would strictly decrease. By moving the shorter pointer, you at least have a chance of finding a taller line that compensates for the reduced width.

This greedy argument is subtle but correct: the key insight is that once you compute the area for a pair (left, right), every other pair involving the shorter line and a narrower width is provably worse. So you can safely discard all of those by advancing the shorter-line pointer. This is similar to the elimination argument in Two Sum II but applied to a maximization problem.

The algorithm runs in O(n) time with O(1) space, since each pointer moves at most n-1 times and you only track the running maximum.

Code Solution:

def max_area(height: list[int]) -> int:
    left = 0
    right = len(height) - 1
    best = 0

    while left < right:
        width = right - left
        h = min(height[left], height[right])
        best = max(best, width * h)

        # Move the shorter line inward
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return best

Variant: Sort Colors (Dutch National Flag) (LeetCode 75)

Trap: Don't advance mid after swapping with high — the swapped-in element is unprocessed

Problem Statement: Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red (0), white (1), and blue (2). You must solve this without using the library's sort function. (LeetCode 75)

Hints:

1. This is a three-way partitioning problem. You need three regions: 0s on the left, 2s on the right, 1s in the middle.
2. Use three pointers: low (boundary of 0s), mid (current element), and high (boundary of 2s). This is the Dutch National Flag algorithm.
3. When nums[mid] == 0, swap it to the low region. When nums[mid] == 2, swap it to the high region. When nums[mid] == 1, just advance mid.

Solution Approach:

Initialize three pointers: low = 0, mid = 0, and high = n - 1. The invariant is: everything before low is 0, everything after high is 2, and everything between low and mid is 1. The region from mid to high is unprocessed.

Process elements at mid one by one. If nums[mid] == 0, swap nums[mid] with nums[low], then advance both low and mid. If nums[mid] == 2, swap nums[mid] with nums[high] and decrement high (but do not advance mid, because the swapped-in element is unprocessed). If nums[mid] == 1, just advance mid.

This runs in O(n) time with O(1) space because each element is examined at most twice. It is a classic same-direction two-pointer variant where three pointers partition the array into four regions.

Code Solution:

def sort_colors(nums: list[int]) -> None:
    # Dutch National Flag: three-way partition
    low = 0        # boundary for 0s
    mid = 0        # current element being examined
    high = len(nums) - 1  # boundary for 2s

    while mid <= high:
        if nums[mid] == 0:
            # Swap to the 0s region
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 2:
            # Swap to the 2s region (don't advance mid -- new element unprocessed)
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
        else:
            # nums[mid] == 1, already in the right place
            mid += 1

Pattern Combination: 4Sum (LeetCode 18)

Trap: Duplicate skipping needed at every level (both outer loops + inner pointers), not just one

Problem Statement: Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that a, b, c, and d are distinct indices and nums[a] + nums[b] + nums[c] + nums[d] == target. The solution set must not contain duplicate quadruplets. (LeetCode 18)

Hints:

1. This extends the 3Sum approach by adding one more outer loop. Fix two elements, then use two pointers for the remaining pair.
2. Sort the array first. The two outer loops pick nums[i] and nums[j] (where j > i). The inner two pointers scan the subarray after j for a pair summing to target - nums[i] - nums[j].
3. Skip duplicates at every level: for i, for j, and after finding a valid quadruplet. Also use early termination: if the smallest possible sum with current i exceeds the target, break.

Solution Approach:

Sort the array. Use two nested loops for indices i and j (with j = i + 1). For each (i, j) pair, compute the remaining target remain = target - nums[i] - nums[j] and run the standard two-pointer scan on the subarray nums[j+1..n-1] to find pairs summing to remain.

Duplicate skipping follows the same principle as 3Sum but at more levels. Skip i when nums[i] == nums[i-1] and skip j when nums[j] == nums[j-1] (with j > i + 1). After finding a valid quadruplet, advance both left and right past duplicate values.

For optimization, add early termination: if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target, break the outer loop (all remaining sums will be too large). If nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target, skip this i (even the largest remaining values are too small).

The time complexity is O(n^3): two nested loops of O(n) each, and the two-pointer scan is O(n). Sorting is O(n log n), which is dominated. Space is O(1) beyond the output.

Code Solution:

def four_sum(nums: list[int], target: int) -> list[list[int]]:
    nums.sort()
    n = len(nums)
    result = []

    for i in range(n - 3):
        # Skip duplicate values for first element
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        # Early termination: smallest possible sum too large
        if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
            break
        # Skip: largest possible sum with this i is too small
        if nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target:
            continue

        for j in range(i + 1, n - 2):
            # Skip duplicate values for second element
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            # Early termination for inner loop
            if nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target:
                break
            if nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target:
                continue

            remain = target - nums[i] - nums[j]
            left = j + 1
            right = n - 1

            while left < right:
                two_sum = nums[left] + nums[right]
                if two_sum == remain:
                    result.append([nums[i], nums[j], nums[left], nums[right]])
                    # Skip duplicates for left and right
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif two_sum < remain:
                    left += 1
                else:
                    right -= 1

    return result

Interview Communication Tips

1. State your observation about sorted order early. As soon as you recognize the input is sorted (or can be sorted), say: "Since the array is sorted, I can use two pointers to avoid checking all O(n^2) pairs. The sorted order lets me decide which pointer to move based on whether the current sum is too large or too small." This immediately signals to the interviewer that you understand the pattern.

2. Explain the elimination argument. Interviewers want to know why two pointers is correct, not just fast. Say something like: "When the sum is too large, moving the right pointer left is safe because the current right element paired with any larger left index would produce an even larger sum. So I can eliminate that entire column of possibilities." This proves you understand correctness, not just the mechanics.

3. Discuss the sorting cost explicitly. If the input is unsorted, acknowledge the trade-off: "I will sort first in O(n log n), which dominates the O(n) two-pointer scan, giving O(n log n) overall. This is better than the O(n^2) brute force." Interviewers appreciate awareness of the total cost, not just the scan cost.

4. Prepare for the follow-up: "What if you need all pairs, not just one?" In problems like 3Sum, the interviewer may ask how you handle duplicates. Be ready to say: "After finding a valid pair, I skip over duplicate values for both pointers to avoid adding the same triplet twice. I also skip duplicate values in the outer loop."

5. Know when to suggest alternatives. If the interviewer modifies the problem (e.g., "what if the array is unsorted and you cannot sort it?"), pivot gracefully: "Without sorted order, two pointers loses its elimination property. I would switch to a hash map approach that provides O(n) lookup for the complement."

Common Mistakes

1. Forgetting the array must be sorted. Two pointers for pair-finding only works on sorted data. If the input is unsorted, you must sort it first (and account for that in your complexity analysis). A common bug is applying the technique to an unsorted array and getting wrong answers.

2. Using left <= right instead of left < right. When searching for a pair, the two pointers must point to different elements. Using <= can cause you to use the same element twice. For example, in Two Sum II with array [3, 3] and target 6, left < right correctly finds the pair, while left <= right might try to use the same index twice on a single-element array edge case.

3. Not handling duplicates in 3Sum and similar problems. When the problem says "find all unique triplets," you must skip duplicate values during iteration. Forgetting this leads to duplicate triplets in the output. The fix is to add if i > 0 and nums[i] == nums[i-1]: continue for the outer loop, and similar skip logic after finding a valid pair.

4. Moving the wrong pointer. In problems like Container With Most Water, the correctness depends on moving the pointer at the shorter line. Moving the wrong pointer breaks the greedy argument and can miss the optimal answer. Always reason about why moving a particular pointer cannot miss the answer before coding.

Chapter Summary

• Two pointers works on sorted arrays: opposite-direction for pairs (Two Sum II), same-direction for in-place operations (remove duplicates).
• The elimination argument: each pointer move eliminates an entire row/column of possibilities, reducing O(n²) to O(n).
• Use left < right for pairs (not <=) to avoid using the same element twice.
• Handle duplicates in 3Sum/4Sum by skipping repeated values in outer loops and after finding valid pairs.
• Variants include Dutch National Flag (three-way partition) and Container With Most Water (move the shorter pointer).

Related patterns: Sliding Window, Binary Search