Two Pointers Foundations

8 concept walkthroughs, each with a worked explanation and an interactive visualization, before you start solving problems in this area.

Two Fingers on a Row

A word or a list is a row of boxes, with one letter or number in each box. Every box has an index, its place number, and the counting starts at 0 because the index says how many boxes you step over from the start. The word 'racecar' has 7 letters, so its indexes run from 0 to 6. len('racecar') gives 7, so the last index is len minus 1, which is 6. A pointer is a variable that holds an index. Think of a finger resting on a box: word[left] is the letter under the finger called left. Two pointers means two fingers. Put left on index 0 and right on index 6, compare the two letters, then move both fingers one box toward the middle: left becomes 1 and right becomes 5. Keep going while left < right. In 'racecar' the pairs are r with r, a with a, c with c, and then both fingers stand on the e at index 3, so the loop stops: the middle letter has no partner. A word that reads the same forwards and backwards is called a palindrome, and 'racecar' is one. The code uses def (start a function), return (hand back an answer and stop) and while (repeat as long as the condition is true).

The intuition

Why start at both ends? A word reads the same both ways exactly when its first letter matches its last, its second matches its second from the end, and so on. Those pairs are the outer pair, then the next pair in, so two fingers walking inward visit every pair once and never repeat one. Now count the work. Seven letters need 3 comparisons, 1,000 letters need 500, and 2,000 letters need 1,000. When the word doubles, the steps double. We write that as O(n), read 'order n', where n is the number of items. Big-O is just a short way to say how the steps grow as the row grows; O(n) means in step with n. The two fingers are just two numbers, so they use the same tiny memory for any length.

A real-world analogy

Two friends check that a shelf of 7 books is arranged as a mirror: the first book matches the last, the second matches the second from the end, and so on. One friend starts at the left end, the other at the right end, and they walk toward each other comparing the books in front of them. At the same middle book, nobody is left to compare it with. The friends are the pointers, the shelf places are the indexes, and meeting in the middle is the moment left < right stops being true.

def reads_same(word):                  # def starts a function; word is a row of letters
    left = 0                           # left finger: the first letter
    right = len(word) - 1              # right finger: the last letter (len is 7, so index 6)
    while left < right:                # repeat while the fingers have not met
        if word[left] != word[right]:  # != means 'is not equal to'
            return False               # one mismatch: it cannot read the same both ways
        left = left + 1                # left finger one box to the right
        right = right - 1              # right finger one box to the left
    return True                        # every pair matched
print(reads_same('racecar'), reads_same('racecat'))

Skipping What Does Not Count

Real sentences have spaces, commas and capital letters. For 'Nurses run!' we want to compare only letters and digits and ignore capitals. Python has two helpers for that. A method is a function that belongs to a string and is written after a dot: 'N'.lower() gives 'n'. The method ch.isalnum() answers True when the character ch is a letter or a digit, and False for a space or a punctuation mark: 'n'.isalnum() is True, ' '.isalnum() is False, '!'.isalnum() is False. The word not flips True and False, and the word and is True only when both sides are True. Now the fingers. Before each comparison, step left forward while it stands on junk, and step right backward while it stands on junk. 'Nurses run!' has 11 characters, indexes 0 to 10. The right finger starts on the '!' at index 10, which is junk, so it steps to the n at index 9. Now N and n are compared in small letters, and they match. Each inner loop asks left < right again before it moves a finger, so a finger can never run past the other one or off the end of the text.

The intuition

Why are the skip loops inside the main loop, and why do they ask left < right all over again? Because the main loop checked that question before the skipping, and skipping can move a finger a long way. Take '!!!'. Without the second check, left would walk over every ! and step off the end of the text, which is an IndexError. With the check, the fingers stop as soon as they meet, and a text with nothing to compare counts as a palindrome. Skipping adds no extra work: each finger moves in one direction only, so every character is visited at most once. That is still O(n) steps, with no cleaned-up copy of the text.

A real-world analogy

Two inspectors walk along a long table of parcels from opposite ends. Some places on the table hold only packing paper, which does not count. Each inspector first steps past the paper until standing in front of a real parcel, and only then do the two compare their parcels. If the inspectors bump into each other while stepping past paper, the inspection is over. The inspectors are the fingers, the packing paper is the spaces and punctuation, and bumping into each other is the left < right check.

def is_palindrome(s):
    left = 0
    right = len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():    # step over junk on the left
            left = left + 1
        while left < right and not s[right].isalnum():   # step over junk on the right
            right = right - 1
        if s[left].lower() != s[right].lower():          # compare in small letters
            return False
        left = left + 1
        right = right - 1
    return True
print(is_palindrome('Nurses run!'), is_palindrome('Nurses jog!'), is_palindrome('!!!'))

Sorted Order Tells You Which Finger to Move

A list is sorted when it runs from the smallest value to the largest. Take the prices [1, 3, 4, 6, 8, 11] and ask: which two prices add up to exactly 10? Checking every pair means 15 pairs for 6 prices. Because the list is sorted, two fingers can answer with at most 5 moves. Put left on the smallest price (1) and right on the largest (11), and add them: 1 + 11 = 12, which is too big. Now think. 11 is the biggest price, and even the smallest partner already makes 12, so 11 can never be in a pair that makes 10. Move right one box to the left. Next, 1 + 8 = 9 is too small. 8 is the biggest price still in play, so 1 cannot reach 10 with anybody: move left one box to the right. The rule is short. A total that is too big means move right. A total that is too small means move left. A total that is equal means the pair is found.

The intuition

Each move throws away a price that cannot be in any answer, and it throws away a whole group of pairs at once. Moving right past 11 removes all 5 pairs that contain 11 with a single addition. That is why an answer is never skipped. Now count. Checking every pair takes about n x n / 2 pairs: 15 pairs for 6 prices, 499,500 for 1,000 prices and 4,999,950,000 for 100,000 prices. The two fingers make at most n - 1 moves: 5, 999 and 99,999. That is O(n) against O(n^2), read 'n squared', which means n times n. Sorting is what makes the argument work. In an unsorted row a too-big total says nothing about which finger to move.

A real-world analogy

A shelf of gifts is sorted from the cheapest to the most expensive, and you want exactly two gifts that cost 10 coins together. You stand with one hand on the cheapest gift and one hand on the most expensive. If those two cost too much, the most expensive gift is hopeless, because even the cheapest partner is too much for it, so that hand steps down the shelf. If they cost too little, the cheapest gift is hopeless, so that hand steps up. The hands are the fingers, and the price order on the shelf is the sorted order.

def pair_with_sum(nums, target):      # nums is sorted, smallest first
    left = 0                          # the smallest value still in play
    right = len(nums) - 1             # the largest value still in play
    while left < right:
        total = nums[left] + nums[right]
        if total == target:
            return [left, right]      # found: hand back the two indexes
        if total < target:            # too small: only a bigger left value can help
            left = left + 1
        else:                         # too big: only a smaller right value can help
            right = right - 1
    return []                         # the fingers met: no pair (an empty list)
print(pair_with_sum([1, 3, 4, 6, 8, 11], 10))

The Lower Side Decides

Picture five walls in a row, each one box wide, with heights [3, 0, 2, 0, 4]. The wall at index 0 is 3 tall, index 1 has no wall (height 0), and so on. Water held between two walls can only rise to the lower of the two, because it spills over the shorter one. Python's min(a, b) gives the smaller number and max(a, b) the larger. Choose the walls at index 0 and index 4. The gap is 4 - 0 = 4 wide, the lower wall is min(3, 4) = 3, so the area is 4 x 3 = 12. To search the pairs with two fingers, start at the ends and always move the finger that stands on the lower wall. Why is nothing lost? Wall 0 (height 3) could only pair with walls closer in, the gap would then be at most 3 wide, and the water is still capped at 3, so at most 3 x 3 = 9, which is less than 12. The same row answers a second question: after rain, how much water sits on the row? For each spot, the level is the lower of the tallest wall on its left and the tallest on its right, and the water is that level minus the spot's own height. At index 1 that is min(3, 4) - 0 = 3 units.

The intuition

Both questions follow one law: the lower side decides. For the container, a lower wall can never score better once the gap shrinks, so its finger is the one to move. For the rain, keep two running numbers: left_max is the tallest wall seen from the left end up to the left finger, and right_max is the same from the right end. Suppose left_max is 3 and right_max is 4. A spot under the left finger has a wall at least 4 tall somewhere to its right, so its water level is limited by the left side alone: 3. We can finish that spot now, without knowing the walls in between, and move the left finger. After each move, left_max = max(left_max, new height) keeps the running number up to date. One pass: O(n).

A real-world analogy

Hold two boards upright in a water tank and pour water in between them. The water rises until it reaches the top of the shorter board and then spills over it, so the taller board makes no difference. The boards are the walls, the gap between your hands is the width, and the shorter board is the lower wall. If you want a bigger pool, keeping the shorter board while the gap shrinks gains nothing, so you swap that board for another one.

def best_area(h):                          # h holds the wall heights
    left = 0
    right = len(h) - 1
    best = 0                               # the biggest area seen so far
    while left < right:
        width = right - left               # how far apart the two walls stand
        lower = min(h[left], h[right])     # water stops at the lower wall
        best = max(best, width * lower)    # keep the larger number
        if h[left] < h[right]:             # the left wall is the lower one
            left = left + 1                # so move that finger
        else:
            right = right - 1
    return best
print(best_area([3, 0, 2, 0, 4]))

A Reader and a Writer

Now both fingers walk in the same direction. Take the sorted list nums = [1, 1, 2, 2, 2, 5, 5] and squeeze out the repeats, so each value appears once at the front: [1, 2, 5, ...]. What sits after the front part does not matter. Do it in place, which means inside the same list, without making a second one. Use two fingers. read visits every box from left to right and looks at the value. write marks the next box that is free to receive a kept value. Everything to the left of write is the finished part: the distinct values kept so far. Box 0 is always kept, since nothing stands before it, so write starts at 1, and read starts at 1 too. The list is sorted, so equal values sit side by side, and one comparison, nums[read] against nums[read - 1], tells whether the value is new. If it is new, copy it into nums[write] and move write one box to the right. If not, do nothing. At the end write equals the number of kept values: 3.

The intuition

Why not delete the repeats? nums.pop(i) removes the item at index i, but every item after it has to slide one box to the left to close the gap. That is up to n steps for one removal, and with many repeats it adds up to n x n. The reader and the writer touch each box once: read looks, write stores, nothing slides. That is n steps, O(n), and no second list, so only two extra numbers. The picture to hold is the finished part. After every round, the boxes before write hold exactly the distinct values seen so far, in order. Copying may overwrite a box the reader has already passed, and that is safe because the reader never looks back at it.

A real-world analogy

A librarian has a long shelf of cards sorted by number, with several cards for the same number. One hand walks along the whole shelf, looking at every card (the reader). The other hand keeps the place at the front of the same shelf where the next keeper card will go (the writer). When the reading hand finds a card with a number it has not kept yet, that card is moved to the writing hand's place, and the writing hand steps one place forward. The cards before the writing hand are the finished, duplicate-free part.

def squeeze(nums):
    if len(nums) == 0:                     # an empty list keeps nothing
        return 0
    write = 1                              # box 0 is always kept; box 1 is the next free box
    for read in range(1, len(nums)):       # range(1, 7) gives 1, 2, 3, 4, 5, 6
        if nums[read] != nums[read - 1]:   # a new value: different from its left neighbour
            nums[write] = nums[read]       # copy it into the next free box
            write = write + 1              # the finished part grew by one
    return write                           # how many values were kept
nums = [1, 1, 2, 2, 2, 5, 5]
k = squeeze(nums)
print(k, nums[:k])                         # nums[:k] means the first k boxes

Fix One, Run Two Fingers on the Rest

Now find three numbers that add up to 0 in nums = [2, 0, -2, 2, 0, 2]. Trying every triple is a loop inside a loop inside a loop. Instead, sort first: nums.sort() rearranges the list in place from smallest to largest, giving [-2, 0, 0, 2, 2, 2]. Then fix one number, nums[i], and ask which two numbers to its right add up to the opposite of nums[i]. That is the sorted pair question again, with left = i + 1 and right = the last index. For i = 0 the number is -2, so the pair must make 2, and 0 + 2 works. We store the answer with result.append([-2, 0, 2]); result is a list that holds lists. The same triple must not be reported twice, so there are two skips. If nums[i] equals the one before it, continue jumps straight to the next round of the loop. After a find, move left past boxes equal to the one just used. Also, elif means 'else, if', and range(len(nums) - 2) gives i = 0, 1, 2, 3 for 6 numbers, because i needs two boxes after it.

The intuition

Fixing one number turns a three-number puzzle into the two-finger puzzle you already know. Count the work. There are n choices for i, and for each one the fingers make at most n moves, so about n x n steps: roughly 1,000,000 for 1,000 numbers. Trying every triple takes about n x n x n / 6 triples, which is 166,167,000 for 1,000 numbers. Sorting costs a little more than n steps, about n times the number of times you can halve n; for 1,000 numbers that is roughly 10,000 steps, small next to n x n. So the whole method is O(n^2). Skipping repeated values of i and of left is what keeps the answer free of copies.

A real-world analogy

A hand of cards is spread out sorted by points, and some cards carry negative points. You want three cards whose points cancel to zero. You lay one card on the table (the fixed number) and keep it there. Then you use the two-hand trick on the cards to the right of it, looking for two cards whose points cancel the one on the table. When you have tried all pairs for that card, you pick the next card to lay down, but never one with the same points as the last, because it would give the same triples again.

def three_sum(nums):
    nums.sort()                                    # smallest to largest, in place
    result = []                                    # a list that will hold the triples
    for i in range(len(nums) - 2):                 # i needs two boxes after it
        if i > 0 and nums[i] == nums[i - 1]:       # same value as the last fixed one
            continue                               # skip it: go to the next i
        left = i + 1
        right = len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total < 0:
                left = left + 1
            elif total > 0:                        # elif means 'else, if'
                right = right - 1
            else:                                  # the three add up to 0
                result.append([nums[i], nums[left], nums[right]])
                left = left + 1
                while left < right and nums[left] == nums[left - 1]:
                    left = left + 1                # step past copies of the value just used
    return result
print(three_sum([2, 0, -2, 2, 0, 2]))

Three Zones in One Pass

Six parcels carry a tag of 0, 1 or 2, in this order: [2, 0, 2, 1, 1, 0]. Rearrange the same row so all the 0s come first, then the 1s, then the 2s, with a single walk. Use three fingers and think in zones. low is the first box not yet known to be a 0, so everything before low is a 0. high is the last box not yet known to be a 2, so everything after high is a 2. mid is the finger that reads: it walks through the middle, the boxes from low up to just before mid are all 1s, and the boxes from mid to high are still unknown. Start with low = 0, mid = 0, high = 5: all six boxes are unknown. Look at the tag under mid. A 0 swaps with the box at low, and then low and mid both move forward. A 1 is already in the right zone, so mid moves forward. A 2 swaps with the box at high, and only high moves back. The swap line is a, b = b, a, which swaps two boxes at once: nums[low], nums[mid] = nums[mid], nums[low]. Writing nums[low] = nums[mid] first would erase a value.

The intuition

Why does mid stay put after a swap with high? The box that arrives at mid came from the unknown zone, and nobody has looked at it yet; it could be 0, 1 or 2. Why does mid move after a swap with low? The box that arrives from low is already known to be a 1 (or it is mid's own box when low and mid stand together), so it belongs in the 1 zone. Why mid <= high and not mid < high? When mid and high stand on the same box, that box is still unknown and must be read. Every round either mid moves forward or high moves back, so the unknown zone shrinks by one each time. That is at most n rounds: one pass, O(n), with three extra numbers.

A real-world analogy

A table holds six shirts in three colours that a helper must sort into three zones: red on the left, white in the middle and blue on the right. The helper stands in the middle zone with a free hand pointing at the next unsorted shirt. A red one is swapped with the first white spot and the red zone grows. A white one needs no move. A blue one is swapped with the last unsorted spot, and the helper must look at the shirt that just arrived. The red, white and blue zones are the 0, 1 and 2 zones.

nums = [2, 0, 2, 1, 1, 0]
low = 0                      # everything before low is a 0
mid = 0                      # the finger that reads; low..mid-1 are all 1s
high = len(nums) - 1         # everything after high is a 2
while mid <= high:           # boxes mid..high are still unknown
    if nums[mid] == 0:
        nums[low], nums[mid] = nums[mid], nums[low]    # swap the two boxes
        low = low + 1
        mid = mid + 1
    elif nums[mid] == 1:
        mid = mid + 1
    else:
        nums[mid], nums[high] = nums[high], nums[mid]
        high = high - 1      # mid stays: the box that arrived is unknown
print(nums)

How Far Must This Piece Reach?

A string is a row of letters. Cut s = 'xyxzwzabcbk' (11 letters, indexes 0 to 10) into pieces from left to right so that no letter appears in two pieces, with as many pieces as possible. The answer is the length of each piece. A piece that holds a letter must hold every copy of that letter, so for each letter we need its last index. A Python dictionary (dict) stores facts like that: it is a table of key and value pairs. last = {} makes an empty one, last['x'] = 2 stores the value 2 under the key 'x', last['x'] reads it back, and storing again under the same key overwrites the old value. A loop that runs last[s[i]] = i for every index leaves each letter with its last index: x is 2, y is 1, z is 5, w is 4, a is 6, b is 9, c is 8, k is 10. Then walk again with i. start is where the current piece begins, and end is how far it must reach. Each letter pushes end out to max(end, last[letter]). When i reaches end, no letter inside reaches further, so cut there. The length is end - start + 1, because both ends count: boxes 3 to 5 are 5 - 3 + 1 = 3 boxes.

The intuition

A cut after index i is allowed exactly when every letter seen so far has its last copy at index i or earlier. Cutting at the first moment that is true gives the most pieces, because waiting longer can only make a piece longer and the pieces fewer. The end finger is a running maximum: it only grows while a piece is being read, and it stops growing when i catches up with it. Count the work: one walk to fill the dict and one walk to cut, so 2 x n steps, which we still write as O(n). The dict has one entry per different letter, at most 26 for lowercase letters, and looking up a key takes about one step on average.

A real-world analogy

A shelf holds books from several series, and the shelf must be cut into sections so every series stays inside one section. First you note down, for each series, the position of its last volume. Then you walk along the shelf from the left: a section has to stretch to the last volume of every series it already contains. The notebook is the dictionary, the section start is start, the farthest last volume so far is end, and the moment your walk reaches that volume is the cut.

def piece_lengths(s):
    last = {}                              # a dict: letter -> its last index
    for i in range(len(s)):
        last[s[i]] = i                     # a copy further right overwrites an earlier one
    sizes = []
    start = 0                              # where the current piece begins
    end = 0                                # how far the current piece must reach
    for i in range(len(s)):
        end = max(end, last[s[i]])         # the last copy of this letter must be inside
        if i == end:                       # no letter reaches past here: cut
            sizes.append(end - start + 1)  # the piece covers start..end
            start = i + 1                  # the next piece begins after the cut
    return sizes
print(piece_lengths('xyxzwzabcbk'))

All DSA learning paths