I am working my way through a classic book of programming puzzles. As I work through more of these puzzles, I’ll share what I discover to solidify my understanding and help others who are doing the same. If you’ve ever completed puzzles on a site like leetcode, you’ll notice that the sheer volume of puzzles is overwhelming. However, there are patterns to these puzzles, and becoming familiar with them makes it easier to solve them. In this post we’ll take a look at one such pattern - two pointers - and see how it can be used to solve puzzles involving arrays.

## Two Pointers

The idea behind two pointers is that there are, as the name suggests, two pointers that traverse the array, with one pointer leading the other. Using these two pointers we update the array and solve the puzzle at hand. As an illustrative example, let us consider the puzzle where we’re given an array of even and odd numbers and we’d like to move all the even numbers to the front of the array.

### Even and Odd

1 | def even_odd(A: list[int]) -> None: |

The two pointers here are `idx`

and `write_idx`

. While `idx`

traverses the array and indicates the current element, `write_idx`

indicates the position where the next even number should be written. Whenever `idx`

points to an even number, it is written at the position indicated by `write_idx`

. With this logic, if all the numbers in the array are even, `idx`

and `write_idx`

point to the same element i.e. the number is swapped with itself and the pointers are moved forward.

We’ll build upon this technique to remove duplicates from the array.

### Remove Duplicates

Consider a sorted array containing duplicate numbers. We’d like to keep only one occurrence of each number and overwrite the rest. This can be solved using two pointers as follows.

1 | def remove_duplicates(A: list[int]) -> int: |

In this solution, `idx`

and `write_idx`

start at index 1 instead of 0. The reason is that we’d like to look at the number to the left of `write_idx`

, and starting at index 1 allows us to do that. Notice also how we’re writing the `if`

condition to check for duplicity in the vicinity of `write_idx`

; the number to the left of `write_idx`

should be different from the one that `idx`

is presently pointing to.

As a varitation, move the duplicates to the end of the array instead of overwriting them.

1 | def remove_duplicates(A: list[int]) -> None: |

As another variation, remove a given number from the array by moving it to the end.

1 | def remove(A: list[int], k: int) -> None: |

With this same pattern, we can now change the puzzle to state that we want at most two instances of the number in the sorted array.

### Remove Duplicates Variation

1 | def remove_duplicates(A: list[int]) -> int: |

Akin to the previous puzzle, we look for duplicates in the vicinity of `write_idx`

. While in the previous puzzle the `if`

condition checked for one number to the left, in this variation we look at two positions to the left of `write_idx`

to keep at most two instances. The remainder of the logic is the same. As a variation, try keeping at most three instances of the number in the sorted array.

Finally, we’ll use the same pattern to solve the Dutch national flag problem.

### Dutch National Flag

In this problem, we sort the array by dividing it into three distinct regions. The first region contains elements less than the pivot, the second region contains elements equal to the pivot, and the third region contains elements greater than the pivot.

1 | def dutch_national_flag(A: list[int], pivot_idx: int) -> None: |

This problem combines everything we’ve seen so far about two pointers and divides the array into three distinct regions. As we compute the first two regions, the third region is computed as a side-effect.

We can now solve a variation of the Dutch national flag partitioning problem by accepting a list of pivot elements. In this variation all the numbers within the list of pivots appear together i.e. all the elements equal to the first pivot element appear first, equal to second pivot element appear second, and so on.

1 | def dutch_national_flag(A: list[int], pivots: list[int]) -> None: |

That’s it, that’s how we can solve puzzles involving two pointers and arrays.