Lesson 2 of 16 Arrays and Strings

Two Pointers Pattern

Two pointers pattern for sorted and symmetric arrays: pair sum, 3Sum without duplicates and container with most water, with the reasoning for each move.

35-45 min beginner 0/16 lessons done
Course contents Lesson 2 of 16 · 0 done
On this page (9 sections)
  1. What you will learn
  2. Signals
  3. Template
  4. Code
  5. Why the moves are safe
  6. Variants
  7. Key takeaways
  8. Exercises
  9. Quiz

What you will learn

  • When two pointers replace a nested loop.
  • How to argue that moving a pointer never skips the answer.
  • 3Sum with duplicate handling, and container with most water.

Signals

  • The input is sorted (or you can sort it) and you need pairs or triples with a target sum.
  • The problem is symmetric: palindromes, reversing, comparing both ends.
  • You need to partition in place (move zeroes, Dutch flag).

Template

lo, hi = 0, len(a) - 1
while lo < hi:
    if condition_met(a[lo], a[hi]):
        record_answer()
    elif need_bigger:
        lo += 1
    else:
        hi -= 1

Each step discards one element for good, so the loop is O(n).

Code

"""Two pointers on sorted or symmetric input."""


def pair_with_sum(sorted_nums, target):
    lo, hi = 0, len(sorted_nums) - 1
    while lo < hi:
        s = sorted_nums[lo] + sorted_nums[hi]
        if s == target:
            return lo, hi
        if s < target:
            lo += 1   # need a bigger sum: only moving lo right can help
        else:
            hi -= 1   # need a smaller sum
    return None


def three_sum(nums):
    nums = sorted(nums)
    out = []
    for i in range(len(nums) - 2):
        if i and nums[i] == nums[i - 1]:
            continue  # skip duplicate anchors
        lo, hi = i + 1, len(nums) - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                out.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
    return out


def max_water(heights):
    lo, hi, best = 0, len(heights) - 1, 0
    while lo < hi:
        best = max(best, (hi - lo) * min(heights[lo], heights[hi]))
        if heights[lo] < heights[hi]:
            lo += 1  # the shorter wall limits the area; moving the taller one can't help
        else:
            hi -= 1
    return best


if __name__ == "__main__":
    print(pair_with_sum([1, 3, 4, 6, 8, 11], 10))
    print(three_sum([-1, 0, 1, 2, -1, -4]))
    print(max_water([1, 8, 6, 2, 5, 4, 8, 3, 7]))

Output:

(2, 3)
[[-1, -1, 2], [-1, 0, 1]]
49

Why the moves are safe

  • Pair sum: if a[lo] + a[hi] is too small, pairing a[lo] with anything left of hi is even smaller, so a[lo] can’t be in any answer. Discard it.
  • 3Sum: sort, fix the first number, then run pair sum on the rest. Skip equal anchors and equal lo values to avoid duplicate triples. O(n²) overall, the best known for this problem in practice.
  • Container with most water: the area is limited by the shorter wall. Moving the taller wall inward can only shrink the width without raising that limit, so always move the shorter one.

Being able to state this “why” is what interviewers listen for.

Variants

  • Same direction (read/write pointers): remove duplicates in place, move zeroes. One pointer scans, the other marks where to write.
  • Opposite ends on strings: valid palindrome, reverse vowels.
  • When the window between pointers must satisfy a condition, that’s the sliding window pattern.

Practise: two pointers problems.

Key takeaways

  • Two pointers work when each comparison lets you discard an element for good.
  • Sort first if order doesn’t matter to the answer; it costs O(n log n).
  • In 3Sum, deduplicate by skipping equal neighbours, not by using a set of tuples.
  • Always be able to explain why a pointer move can’t skip the answer.

Exercises

  1. Solve “valid palindrome” ignoring non-alphanumeric characters with two pointers.
  2. Write “move zeroes” with read/write pointers, keeping the order of non-zero elements.
  3. Extend three_sum to 4Sum. What’s the complexity?

Quiz

  1. Why must the array be sorted for pair sum with two pointers?
  2. In container with most water, why move the shorter wall?
  3. What’s the time complexity of 3Sum with this approach?
Show answers
  1. Sorting guarantees that moving lo right increases the sum and moving hi left decreases it, which is what makes discarding safe.
  2. The shorter wall caps the height; moving the taller wall can only reduce width while the cap stays the same or lower.
  3. O(n²): O(n log n) to sort plus an O(n) scan for each of n anchors.

Finished this lesson?

Mark it complete to track your progress (saved in this browser).