📊 We use cookies & analytics to improve your experience. Learn more
Latest

Interview DSA Crash Course Module 2 · Lesson 5 of 15

0% Exit to course

Module 2 · Arrays, strings and hashing Lesson 5 of 15

Two pointers

Learning objective

Two positions moving through one sequence, usually from both ends or at different speeds. It turns a nested loop into a single pass.

The concept

Two pointers is one loop with two moving positions instead of two nested loops. Starting at both ends is for a sorted array and a target sum: if the sum is too small, move the left pointer up; too big, move the right one down. Running one behind the other is for removing duplicates in place or reversing part of a sequence.

The reason it works is that each pointer only moves forward, so the whole thing is one pass — O(n) time and no extra memory. The trick to explaining it is the invariant: "everything to the left of the slow pointer is processed, and the fast one is looking for the next item to keep".

Python
def two_sum_sorted(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      # need bigger -> move left up
        else:           right -= 1     # need smaller -> move right down
    return []

# Sorted input required. One pass: O(n) time, O(1) extra space.

Common mistakes

The mistakes are forgetting the pointers may cross — the loop condition is usually while (left < right) — and trying to use the two-ended version on an unsorted array, where moving a pointer tells you nothing. Sort first if the question allows it, and say that you did.

Worked example

Sorted array, find a pair summing to a target: move the left pointer up when the sum is too small and the right pointer down when it is too large — O(n), and it is O(n²) if you look at every pair.

Your practice task

Solve reverse-a-string-in-place, check-for-palindrome and pair-sum with two pointers, and write the complexity under each.

Do this before moving on. Reading a solution teaches the shape of it; typing it teaches you.

Key takeaway

Two pointers is one loop with two moving positions instead of two nested loops.

Create free account or sign in

Almost there

15 lessons left of 15

Finish every lesson to unlock the certificate. Each one ends in a practice task — do them and the final project brief writes itself.