Two Pointers and Monotonic Search Decisions

The two-pointer technique uses two indexes that move through an array, usually one from each end toward the middle, or both from the start at different speeds. Each step looks at the elements under the pointers and moves one of them. Since neither pointer ever goes backwards, the whole thing takes O(n) steps, which often replaces an O(n²) search over every pair.

What makes it work isn’t the pointers. It’s the decision rule. Every time you move a pointer, you’re throwing away a whole set of candidate answers without checking them. That’s only allowed if you can prove none of them could be the answer. If you can say why a move is safe, the technique is correct. If you can’t, it’s a guess that happens to pass the examples.

Pair sum on a sorted array

Given a sorted array and a target, find two values that add up to the target. Put left at the start and right at the end. Look at their sum:

• If it equals the target, you’re done.
• If it’s too small, move left right.
• If it’s too big, move right left.

def pair_with_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        if s < target:
            left += 1                    # nums[left] can't reach target with anything left of right
        else:
            right -= 1                   # nums[right] overshoots even with the smallest partner
    return None

With a trace added, searching [1, 3, 4, 6, 8, 11] for 10:

left=0 (1) right=5 (11) sum=12  too big -> right -= 1
left=0 (1) right=4 (8) sum=9  too small -> left += 1
left=1 (3) right=4 (8) sum=11  too big -> right -= 1
left=1 (3) right=3 (6) sum=9  too small -> left += 1
left=2 (4) right=3 (6) sum=10  found
[2, 3]

Now the proof, which is what the interviewer actually wants to hear. Look at the first step: 1 + 11 = 12 is too big. Moving right discards every pair that uses 11. Is that safe? The smallest partner 11 could have is 1, the current left, and even that overshoots. Every other remaining partner is larger, so every pair with 11 overshoots too. Discarding them loses nothing. The second step is the mirror image: 1 + 8 = 9 is too small, and 8 is the largest partner 1 has left, so 1 can’t reach 10 with anyone. Each step eliminates a whole row or column of the pair grid in one comparison, and that’s why the search is linear.

The argument depends entirely on the array being sorted. Run the same code on the same numbers shuffled:

unsorted input: None  (4 + 6 is there)

With [8, 1, 11, 4, 3, 6], the first sum is 8 + 6 = 14, too big, so the code discards 6, assuming it’s the largest value left. It isn’t, and the pair 4 + 6 is gone. On unsorted input, either sort first (O(n log n), and you lose the original indexes unless you keep them) or use a hash map, as in Two Sum, which is O(n) time but O(n) space.

Container With Most Water: move the shorter line

Container With Most Water gives you heights of vertical lines and asks for the two lines that, together with the x-axis, hold the most water. The area between lines i and j is (j - i) × min(height[i], height[j]).

Start with the widest container, the two outermost lines. Then move the pointer at the shorter line inward:

def max_area(height):
    left, right, best = 0, len(height) - 1, 0
    while left < right:
        best = max(best, (right - left) * min(height[left], height[right]))
        if height[left] < height[right]:
            left += 1                    # the shorter line can't do better with any closer partner
        else:
            right -= 1
    return best

49 1
3,000 random inputs: matches the O(n^2) brute force

That’s [1, 8, 6, 2, 5, 4, 8, 3, 7] and [1, 1], plus a randomised check against trying every pair. Why is moving the shorter line safe? Suppose height[left] is the shorter one. Any other container that uses line left pairs it with some line between the two pointers, so it’s narrower. Its height is capped by height[left], because the water can’t rise above the shorter side. Narrower and no taller means no more water. So line left has already formed its best possible container, the one just measured, and can be discarded.

Moving the taller line instead would be wrong: the width shrinks and the height is still capped by the same short line, so you’d skip containers that might be better. When the two heights are equal, moving either is fine, because both lines have now hit their best possible container.

Same direction: a reader and a writer

The other common shape has both pointers start at the beginning. One, read, scans every element. The other, write, marks where the next kept element goes. Move Zeroes is the standard example: move all zeros to the end while keeping the other values in order, in place.

def move_zeroes(nums):
    write = 0                            # everything before write is non-zero, in original order
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

[1, 3, 12, 0, 0] [0] [4, 2, 5, 0, 0, 0]

The comment states the invariant. Each non-zero value gets swapped down to write, and write advances, so the prefix before write stays non-zero and in order. Swapping, rather than just copying, leaves the zeros at the end without a second pass. It’s O(n) time and O(1) extra space, the same pattern behind removing duplicates from a sorted array or filtering a list in place.

3Sum: one loop plus two pointers

3Sum asks for every unique triplet that sums to zero. Brute force is O(n³). Sorting first lets you fix the first number and run the pair-sum search on the rest for the remaining two:

def three_sum(nums):
    nums = sorted(nums)
    out = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue                     # same first value as last time: same triplets
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s < 0:
                left += 1
            elif s > 0:
                right -= 1
            else:
                out.append([nums[i], nums[left], nums[right]])
                left += 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1            # skip repeats of the second value
                right -= 1
    return out

[[-1, -1, 2], [-1, 0, 1]] [[0, 0, 0]] [] [[-2, 0, 2]]

Those are [-1, 0, 1, 2, -1, -4], [0, 0, 0, 0], [0, 1, 1] and [-2, 0, 0, 2, 2]. The duplicate handling is where most bugs live. Skipping a repeated first value avoids generating the same triplets twice. After a match, skipping repeated second values does the same for the inner pair; once the second value is fixed, the third is determined, so it doesn’t need its own skip loop. Time is O(n²): n outer iterations, each with a linear two-pointer scan. Sorting’s O(n log n) is absorbed. Extra space is O(1) apart from the output, or O(n) if you count the sorted copy.

Interview practice: valid palindrome

Return whether a string is a palindrome after converting letters to lowercase and ignoring everything that isn’t a letter or digit. "A man, a plan, a canal: Panama" is a palindrome; "race a car" isn’t. Use O(1) extra space.

Answer

Building a cleaned copy and comparing it with its reverse works but uses O(n) space. Instead, walk two pointers inward from both ends. If either pointer is on a character that doesn’t count, skip it. Otherwise compare the two characters case-insensitively; a mismatch means it’s not a palindrome, and a match means both pointers move.

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if not s[left].isalnum():
            left += 1                    # skip punctuation and spaces on the left
        elif not s[right].isalnum():
            right -= 1                   # ...and on the right
        elif s[left].lower() != s[right].lower():
            return False
        else:
            left += 1
            right -= 1
    return True

tests = ["A man, a plan, a canal: Panama", "race a car", " ", "0P", ".,", "ab_a"]
print([is_palindrome(t) for t in tests])

[True, False, True, False, True, True]
isalpha version on '0P': True

The decision rule is safe for the same reason as before: when the outer characters match, no palindrome check can be affected by them again, so discarding both is fine; when one is punctuation, it never affects the answer. Strings with no alphanumerics at all, like " " and ".,", count as palindromes because nothing is left to compare.

The "0P" case is in the test list on purpose. A version that uses isalpha() instead of isalnum() skips the digit 0, compares nothing, and wrongly returns True, which is the second line of output. Digits count in this problem. Time is O(n), since each step moves at least one pointer inward; space is O(1). Practise it on Valid Palindrome, then try Trapping Rain Water, whose two-pointer solution uses the same “move the side with the smaller limit” reasoning as the container problem.

More on this topic

• Data Structures and Algorithms interview questions
• DSA multiple-choice questions
• Sliding Windows and Validity Invariants, two pointers moving the same way with a rule
• Binary Search and Explicit Boundaries, another way to exploit sorted order
• MIT 6.006 Introduction to Algorithms (Spring 2020)