Two Pointers in Python. Part of the Data Structures & Algorithms with Python roadmap
This is the second article in the Arrays & Strings cluster. It builds on Arrays in Python: Operations, Complexity, and Common Patterns, so read that one first if you haven’t.
In the last article, you learned that arrays are fast to read and slow to change near the front. You also saw a short preview of five array patterns. The first one was two pointers.
Two pointers turns many O(n²) nested-loop problems into O(n) by moving two index variables through the data by a fixed rule. In this tutorial you will build a small, fully tested toolkit of two-pointers functions and measure how much faster they are.
What you’ll build and learn
You will build a toolkit of two-pointers functions, check each one against a slow brute-force version, and measure the speed difference. By the end, you’ll be able to:
- Explain why two pointers can turn an O(n²) nested loop into an O(n) loop
- Recognize the three pointer patterns: opposite-direction, same-direction, and fast and slow
- Solve pair sum, reverse, palindrome, remove duplicates, merge, linked-list middle and three sum with them
- Test each solution with pytest, including random checks against brute force
- Tell when two pointers does not apply, and spot the bugs that break it
Prerequisites: You should know Python lists, loops and functions, and have a basic idea of Big O notation. You should also be comfortable running pytest from a terminal. The code was run on Python 3.13.
Get the code
The complete, tested project for this tutorial is on GitHub. Clone it and follow along, or build each file as you read.
The idea in one picture
Imagine a hallway of lockers sorted by the number on the door, and you need two lockers whose numbers add up to 13. You stand at the first locker and a friend stands at the last. You add your two numbers. If the sum is too small, you step forward. If it is too big, your friend steps back. You stop when the sum is right or when you meet.
That is the two pointers technique. You keep two index variables, which in Python are usually plain integer indexes, not memory addresses, and move them through a sequence by a fixed rule. Every move throws away an item that cannot be part of the answer, so the total number of moves is limited by the length of the input.
Every two pointers solution follows the same four steps:
- Place the pointers. Decide where each one starts, often at both ends or both at the start.
- Look at the items they point to. Compare them, add them, or check a condition.
- Move a pointer. Use a rule that says which one.
- Stop at the right time. Usually when the pointers meet or cross, or when one reaches the end.
Step 1: Set up the project
The project is a flat folder of small modules, so every import is a plain module name and every command runs from one place. Create the folder, a virtual environment, and install pytest:
$ mkdir two_pointers
$ cd two_pointers
$ python -m venv venv
$ source venv/bin/activate
(venv) $ python -m pip install pytestOn Windows, activate the environment with venv\Scripts\activate instead. You will create these files as you go:
two_pointers/
├── brute_force.py
├── two_pointers.py
├── linked_list.py
├── practice.py
├── pitfalls.py
├── benchmark.py
├── test_two_pointers.py
├── test_linked_list.py
├── test_practice.py
└── test_pitfalls.pytwo_pointers.py is the toolkit, and the other modules support it. brute_force.py holds slow, obviously correct solutions that serve two jobs: a speed baseline, and a test oracle that your fast code must agree with. Each test_ file turns the claims in this tutorial into checks that pass or fail.
The tests in this tutorial use random.Random(seed) with a fixed seed, so a failure is reproducible and shows the same input every time.
git clone https://github.com/Emmimal/two-pointers-python.git
cd two-pointers-python
python -m venv venv
source venv/bin/activate
python -m pip install -r requirements.txt
python -m pytestStep 2: Measure a brute-force baseline
Before you speed something up, measure it. Here is the problem: given a sorted list and a target, find two numbers that add up to the target and return their positions. The first idea most people have is to check every pair. Save this as brute_force.py:
"""Slow but obviously correct solutions, used as a baseline and as a test oracle."""
def pair_sum_brute(nums: list[int], target: int) -> list[int]:
"""Return positions of two numbers that add up to target, or []."""
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []
def three_sum_brute(nums: list[int]) -> list[list[int]]:
"""Return all unique triplets that add up to zero, each sorted."""
n = len(nums)
found: set[tuple[int, int, int]] = set()
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if nums[i] + nums[j] + nums[k] == 0:
smallest, middle, largest = sorted((nums[i], nums[j], nums[k]))
found.add((smallest, middle, largest))
return [list(triplet) for triplet in sorted(found)]This works, but it checks n × (n − 1) / 2 pairs. For 10,000 numbers that is 49,995,000 pairs. three_sum_brute() is here for Step 7, where it will act as the oracle for a faster version.
Now measure the cost. Save this as benchmark.py. It compares the brute force against the two pointers function you will write in Step 3:
"""Time the brute force pair sum against the two pointers version."""
from collections.abc import Callable
from time import perf_counter
from brute_force import pair_sum_brute
from two_pointers import pair_with_target_sum
def time_it(
func: Callable[[list[int], int], list[int]], nums: list[int], target: int
) -> float:
"""Return how many seconds one call to func takes."""
start = perf_counter()
func(nums, target)
return perf_counter() - start
def main() -> None:
print(f"{'n':>7} {'nested loops':>13} {'two pointers':>13}")
for n in (1_000, 2_000, 4_000, 8_000):
# Even numbers only, and an odd target: no pair can ever match, so
# both functions have to do all of their work.
nums = list(range(0, 2 * n, 2))
target = 1
slow = time_it(pair_sum_brute, nums, target)
fast = time_it(pair_with_target_sum, nums, target)
print(f"{n:>7,} {slow:>12.4f}s {fast:>12.6f}s")
if __name__ == "__main__":
main()The input is built so that no pair can match, which forces both functions to do all of their work. Come back and run this file after Step 3. Here is one run on Python 3.13:
(venv) $ python benchmark.py
n nested loops two pointers
1,000 0.0278s 0.000096s
2,000 0.1266s 0.000184s
4,000 0.4222s 0.000355s
8,000 2.1651s 0.000729sYour times will differ, and individual runs are noisy, but the shape should hold. Each time n doubles, the nested loops take roughly four times as long, which is the signature of O(n²). The two pointers time roughly doubles, which is O(n). At 8,000 items the nested loops took about 2.2 seconds, and two pointers took under a millisecond.
Why two pointers is faster
Nested loops forget what they learned. They check a pair, throw away the result, and check the next pair. Two pointers uses each comparison to throw away items for good. When the sum is too small, the left item can never work with anything still in play, so it is dropped and never looked at again.
Each round of the loop moves one pointer by one place, so the loop runs at most n − 1 times. That is an upper limit, and the loop can stop earlier when it finds the answer.
Step 3: Pair sum with opposite-direction pointers
Opposite-direction pointers start at both ends of the sequence and walk toward each other. Use them when the input is sorted and you need a pair, when you compare the two ends, as in a palindrome, or when you swap items from both ends, as in a reversal.
For the pair sum, the sorted order is what makes the rule work. The left pointer holds the smallest value in play and the right pointer holds the largest. Add them:
- If the sum is too small, the left item is too small to work with anything still in play, because every other item is at most the right item. Drop it and move
leftforward. - If the sum is too big, the right item is too big to work with anything still in play, because every other item is at least the left item. Drop it and move
rightbackward. - If the sum is equal, you are done.
Save this as two_pointers.py:
"""A small toolkit of two pointers solutions."""
def pair_with_target_sum(sorted_nums: list[int], target: int) -> list[int]:
"""Return positions of two numbers in a sorted list that add up to target.
Returns an empty list when no such pair exists.
"""
left, right = 0, len(sorted_nums) - 1
while left < right:
total = sorted_nums[left] + sorted_nums[right]
if total == target:
return [left, right]
if total < target:
# The list is sorted, so the left item is too small to pair with
# anything still in play. Drop it for good.
left += 1
else:
# The right item is too big to pair with anything still in play.
right -= 1
return []The loop condition left < right matters. It stops the loop when the pointers meet, so an item is never paired with itself. Try it in the REPL:
>>> from two_pointers import pair_with_target_sum
>>> pair_with_target_sum([1, 3, 5, 8, 11], 13)
[2, 3]
>>> pair_with_target_sum([1, 3, 5, 8, 11], 100)
[]Trace the first call to see which pointer moves and why:
| Step | left | right | nums[left] | nums[right] | Sum | What happens |
|---|---|---|---|---|---|---|
| 1 | 0 | 4 | 1 | 11 | 12 | Too small, move left |
| 2 | 1 | 4 | 3 | 11 | 14 | Too big, move right |
| 3 | 1 | 3 | 3 | 8 | 11 | Too small, move left |
| 4 | 2 | 3 | 5 | 8 | 13 | Found it |
It takes 4 steps. The time is O(n) and the extra space is O(1), because you only store two indexes.
Test it against the brute force
One example passing proves little. A stronger check is to run both versions on thousands of random sorted lists and require them to agree. Save this as test_two_pointers.py:
import random
import pytest
from brute_force import pair_sum_brute
from two_pointers import pair_with_target_sum
def test_pair_sum_finds_the_pair() -> None:
assert pair_with_target_sum([1, 3, 5, 8, 11], 13) == [2, 3]
def test_pair_sum_returns_empty_list_when_there_is_no_pair() -> None:
assert pair_with_target_sum([1, 3, 5, 8, 11], 100) == []
@pytest.mark.parametrize("nums", [[], [7]])
def test_pair_sum_handles_fewer_than_two_items(nums: list[int]) -> None:
assert pair_with_target_sum(nums, 7) == []
def test_pair_sum_does_not_pair_an_item_with_itself() -> None:
assert pair_with_target_sum([4], 8) == []
def test_pair_sum_works_with_negative_numbers() -> None:
assert pair_with_target_sum([-4, -1, 0, 3, 10], 9) == [1, 4]
def test_pair_sum_agrees_with_brute_force_on_random_sorted_lists() -> None:
rng = random.Random(42)
for _ in range(2_000):
nums = sorted(rng.randint(-20, 20) for _ in range(rng.randint(0, 12)))
target = rng.randint(-30, 30)
fast = pair_with_target_sum(nums, target)
slow = pair_sum_brute(nums, target)
# The two may pick different pairs, but they must agree on whether
# a pair exists, and any pair they return must really add up.
assert bool(fast) == bool(slow)
if fast:
i, j = fast
assert i < j
assert nums[i] + nums[j] == targetThe random test compares existence rather than the exact pair, because both functions can find a different valid pair when several exist. Run it, then run the benchmark from Step 2:
(venv) $ python -m pytest
(venv) $ python benchmark.pyThe tests also show that negative numbers are fine. As long as the list is sorted, the same code works.
It needs sorted input
This rule is the one thing the technique cannot do without. On an unsorted list, “too small, so drop the left item” is no longer true, and the function can miss a pair that exists:
>>> from brute_force import pair_sum_brute
>>> pair_with_target_sum([1, 3, 2], 4)
[]
>>> pair_sum_brute([1, 3, 2], 4)
[0, 1]Nothing raises an error, you just get a wrong answer. Add this test to test_two_pointers.py so the lesson stays in the suite:
def test_pair_sum_gives_wrong_answers_on_unsorted_input() -> None:
# 1 + 3 = 4 exists, but the "too small, move left" rule needs sorted data.
assert pair_with_target_sum([1, 3, 2], 4) == []
assert pair_sum_brute([1, 3, 2], 4) == [0, 1]Step 4: Reverse a list and check a palindrome
Two more problems use the same opposite-direction shape, and neither needs sorted input. They show that the technique is about the movement rule, not about sorting.
Reverse a list in place
Swap the first and last items, then the second and second-to-last, and keep going until the pointers meet. Add this to two_pointers.py:
def reverse_in_place(items: list[int]) -> None:
"""Reverse a list without creating a new one."""
left, right = 0, len(items) - 1
while left < right:
items[left], items[right] = items[right], items[left]
left += 1
right -= 1With 5 items, the pointers meet at the middle item, index 2. The loop stops because left < right is no longer true, and the middle item stays where it is, which is correct because it has nothing to swap with. The time is O(n) with n / 2 swaps, and the extra space is O(1).
>>> from two_pointers import reverse_in_place
>>> nums = [1, 2, 3, 4, 5]
>>> reverse_in_place(nums)
>>> nums
[5, 4, 3, 2, 1]The function returns None because it changes the list it was given. That is a design choice worth stating in your docstring, and the test below checks it.
Check a palindrome
A palindrome reads the same forward and backward. Compare the first and last characters. If they match, move both pointers inward. If any pair does not match, the answer is False. Characters that are not letters or digits are skipped. Add this to two_pointers.py:
def is_palindrome(text: str) -> bool:
"""Check a string, ignoring case, spaces and punctuation."""
left, right = 0, len(text) - 1
while left < right:
if not text[left].isalnum():
left += 1
continue
if not text[right].isalnum():
right -= 1
continue
if text[left].lower() != text[right].lower():
return False
left += 1
right -= 1
return True>>> from two_pointers import is_palindrome
>>> is_palindrome("A man, a plan, a canal: Panama")
True
>>> is_palindrome("race a car")
False
>>> is_palindrome("")
TrueYou may know the shorter version, text == text[::-1]. It is fine for a quick check, but it builds a new reversed string, so it uses O(n) extra space. The two pointers version uses O(1) extra space and stops at the first mismatch. Every branch moves at least one pointer, which is what guarantees the loop ends.
First update the imports at the top of test_two_pointers.py to from two_pointers import is_palindrome, pair_with_target_sum, reverse_in_place. Then add these tests:
@pytest.mark.parametrize(
"items",
[[], [1], [1, 2], [1, 2, 3, 4, 5], [1, 1, 1]],
)
def test_reverse_in_place_matches_slicing(items: list[int]) -> None:
expected = items[::-1]
reverse_in_place(items)
assert items == expected
def test_reverse_in_place_returns_nothing_and_changes_the_same_list() -> None:
items = [1, 2, 3]
same_list = items
assert reverse_in_place(items) is None
assert same_list == [3, 2, 1]
@pytest.mark.parametrize(
("text", "expected"),
[
("A man, a plan, a canal: Panama", True),
("race a car", False),
("", True),
("a", True),
(".,", True),
("0P", False),
],
)
def test_is_palindrome(text: str, expected: bool) -> None:
assert is_palindrome(text) is expectedThe cases are chosen on purpose: the empty list, one item and two items are the places where pointer loops usually break. The ".," case has no letters at all, and "0P" checks that a digit and a letter are not treated as equal.
Step 5: Same-direction pointers
In the same-direction pattern, both pointers start near the beginning and move forward, but they do different jobs. Think of a teacher checking homework. One hand reads each page, and the other marks where the next good page goes. The reading hand always moves forward, and the writing hand moves only when a good page is found. In code, these are usually named read and write.
Use this pattern to filter items in place, remove duplicates, or merge two sorted lists.
Remove duplicates from a sorted list
Because the list is sorted, equal values sit next to each other. So a new value is simply one that differs from the last value you kept. Add this to two_pointers.py:
def remove_duplicates(sorted_nums: list[int]) -> int:
"""Remove duplicates from a sorted list in place.
Returns how many unique items now sit at the front of the list. The
items after that position are leftovers and should be ignored.
"""
if not sorted_nums:
return 0
write = 1
for read in range(1, len(sorted_nums)):
# Equal values sit side by side in a sorted list, so a new value is
# simply one that differs from the last value we kept.
if sorted_nums[read] != sorted_nums[write - 1]:
sorted_nums[write] = sorted_nums[read]
write += 1
return writewrite starts at 1 because the first item is always unique. read visits every other item once. Each time read finds a value different from the last kept one, the value is copied to write and write moves forward. Try it and look at the whole list, not just the front:
>>> from two_pointers import remove_duplicates
>>> nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
>>> k = remove_duplicates(nums)
>>> k
5
>>> nums[:k]
[0, 1, 2, 3, 4]
>>> nums
[0, 1, 2, 3, 4, 2, 2, 3, 3, 4]The last line shows the leftovers. The function does not clean up the tail, so the caller must use only the first k items. The time is O(n) and the extra space is O(1). Say out loud in an interview that this works only because the list is sorted.
Merge two sorted lists
Put one pointer at the start of each list, take the smaller item, and move that pointer forward. This is the same step used inside merge sort. Add this to two_pointers.py:
def merge_sorted(first: list[int], second: list[int]) -> list[int]:
"""Merge two sorted lists into one new sorted list."""
i = j = 0
merged: list[int] = []
while i < len(first) and j < len(second):
if first[i] <= second[j]:
merged.append(first[i])
i += 1
else:
merged.append(second[j])
j += 1
# The loop stops when one list runs out, so at most one slice has items.
merged.extend(first[i:])
merged.extend(second[j:])
return merged>>> from two_pointers import merge_sorted
>>> merge_sorted([1, 4, 7], [2, 3, 9])
[1, 2, 3, 4, 7, 9]
>>> merge_sorted([], [5, 6])
[5, 6]The time is O(n + m) for lists of length n and m. The extra space is also O(n + m), because the result is a new list. This is the one example in the toolkit that does not run in constant extra space.
Update the import in test_two_pointers.py to include merge_sorted and remove_duplicates, then add these tests:
def test_remove_duplicates_keeps_each_value_once() -> None:
nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
k = remove_duplicates(nums)
assert k == 5
assert nums[:k] == [0, 1, 2, 3, 4]
@pytest.mark.parametrize(
("nums", "expected"),
[([], []), ([5], [5]), ([2, 2, 2], [2]), ([1, 2, 3], [1, 2, 3])],
)
def test_remove_duplicates_edge_cases(nums: list[int], expected: list[int]) -> None:
k = remove_duplicates(nums)
assert nums[:k] == expected
def test_remove_duplicates_agrees_with_sorted_set_on_random_input() -> None:
rng = random.Random(7)
for _ in range(1_000):
nums = sorted(rng.randint(0, 6) for _ in range(rng.randint(0, 15)))
expected = sorted(set(nums))
k = remove_duplicates(nums)
assert nums[:k] == expected
def test_merge_sorted_interleaves_two_lists() -> None:
assert merge_sorted([1, 4, 7], [2, 3, 9]) == [1, 2, 3, 4, 7, 9]
@pytest.mark.parametrize(
("first", "second"),
[([], [5, 6]), ([5, 6], []), ([], []), ([1, 1], [1, 1])],
)
def test_merge_sorted_edge_cases(first: list[int], second: list[int]) -> None:
assert merge_sorted(first, second) == sorted(first + second)
def test_merge_sorted_does_not_change_its_inputs() -> None:
first, second = [1, 4], [2, 3]
merge_sorted(first, second)
assert first == [1, 4]
assert second == [2, 3]Step 6: Fast and slow pointers on a linked list
A linked list does not let you jump to the middle by index, so how do you find the middle in one pass? Start two pointers at the head. The slow one moves 1 step at a time, and the fast one moves 2. When the fast pointer reaches the end, the slow pointer is at the middle. Think of two runners on a straight road: the fast runner reaches the end when the slow runner is about halfway. On a loop, the fast runner would catch the slow one from behind, which is how the same idea detects a cycle.
Save this as linked_list.py:
"""Fast and slow pointers on a singly linked list."""
from __future__ import annotations
from dataclasses import dataclass
@dataclass
class Node:
"""One node of a singly linked list."""
val: int
next: Node | None = None
def from_values(values: list[int]) -> Node | None:
"""Build a linked list from a Python list and return its head."""
head: Node | None = None
for value in reversed(values):
head = Node(value, head)
return head
def find_middle(head: Node | None) -> Node | None:
"""Return the middle node, or the second middle node for an even length."""
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next if slow else None
fast = fast.next.next
return slowThe loop condition checks fast and fast.next, in that order. For an odd number of nodes, fast lands exactly on the last node, so fast.next is None. For an even number, fast runs off the end and becomes None. Checking both keeps fast.next.next from ever touching None. With an even number of nodes there are two middle nodes, and this code returns the second one.
>>> from linked_list import find_middle, from_values
>>> find_middle(from_values([1, 2, 3, 4, 5])).val
3
>>> find_middle(from_values([1, 2, 3, 4])).val
3The time is O(n), because the fast pointer visits each node at most once, and the extra space is O(1). Save these checks as test_linked_list.py:
import pytest
from linked_list import find_middle, from_values
@pytest.mark.parametrize(
("values", "expected"),
[
([1], 1),
([1, 2], 2),
([1, 2, 3], 2),
([1, 2, 3, 4], 3),
([1, 2, 3, 4, 5], 3),
],
)
def test_find_middle_returns_the_second_middle_for_even_lengths(
values: list[int], expected: int
) -> None:
middle = find_middle(from_values(values))
assert middle is not None
assert middle.val == expected
def test_find_middle_of_an_empty_list_is_none() -> None:
assert find_middle(None) is None
def test_find_middle_agrees_with_indexing_on_every_length() -> None:
for length in range(1, 50):
values = list(range(length))
middle = find_middle(from_values(values))
assert middle is not None
assert middle.val == values[length // 2]The last test uses the fact that the middle node, counting the second one for even lengths, always sits at index length // 2. That gives you a way to check the pointer result against plain indexing for every length from 1 to 49.
Step 7: Combine the pieces into three sum
The harder problem is to find all unique triplets in a list that add up to zero. The brute force from Step 2 uses three nested loops, which is O(n³). You can reuse the pair-sum idea instead: sort the list, fix one number with a loop, and run opposite-direction pointers over the rest to find a pair that makes the total zero.
The tricky part is duplicates. Without care, the same triplet appears more than once. There are two places to skip equal values:
- The first number. If it equals the previous first number, every triplet it could start has already been found.
- After recording an answer. Move both pointers past equal values, so the same pair is not recorded again.
Add this to two_pointers.py:
def three_sum(nums: list[int]) -> list[list[int]]:
"""Return all unique triplets that add up to zero.
The input list is not changed.
"""
ordered = sorted(nums)
triplets: list[list[int]] = []
for i in range(len(ordered) - 2):
# Skip a first number we have already used, or we repeat answers.
if i > 0 and ordered[i] == ordered[i - 1]:
continue
left, right = i + 1, len(ordered) - 1
while left < right:
total = ordered[i] + ordered[left] + ordered[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
triplets.append([ordered[i], ordered[left], ordered[right]])
left += 1
right -= 1
# After recording an answer, step past equal values.
while left < right and ordered[left] == ordered[left - 1]:
left += 1
while left < right and ordered[right] == ordered[right + 1]:
right -= 1
return triplets>>> from two_pointers import three_sum
>>> three_sum([-1, 0, 1, 2, -1, -4])
[[-1, -1, 2], [-1, 0, 1]]The outer loop runs n times, and the two pointers inside run in O(n) each time, so the total is O(n²). That is a big step down from the O(n³) brute force. The extra space is O(1), not counting the output and the copy made by sorted(). Sorting itself costs O(n log n), but that is smaller than O(n²), so it does not change the overall bound.
Using sorted(nums) instead of nums.sort() means the caller’s list is not changed. That matters, because a function that quietly reorders its input is a surprise waiting to happen.
This is the function most likely to hide a duplicate bug, so test it hardest. Update the import in test_two_pointers.py to include three_sum and from brute_force import pair_sum_brute, three_sum_brute, then add these tests:
def test_three_sum_finds_unique_triplets() -> None:
assert three_sum([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]]
@pytest.mark.parametrize(
("nums", "expected"),
[([], []), ([0], []), ([0, 0], []), ([0, 0, 0], [[0, 0, 0]]), ([1, 2, 3], [])],
)
def test_three_sum_edge_cases(nums: list[int], expected: list[list[int]]) -> None:
assert three_sum(nums) == expected
def test_three_sum_all_zeros_returns_one_triplet() -> None:
assert three_sum([0] * 10) == [[0, 0, 0]]
def test_three_sum_does_not_change_its_input() -> None:
nums = [3, -1, 2, -2, 0]
three_sum(nums)
assert nums == [3, -1, 2, -2, 0]
def test_three_sum_agrees_with_brute_force_on_random_input() -> None:
rng = random.Random(2026)
for _ in range(500):
nums = [rng.randint(-6, 6) for _ in range(rng.randint(0, 10))]
assert three_sum(nums) == three_sum_brute(nums)The last test is the one that earns its keep. Small numbers from −6 to 6 in short lists produce many repeated values, which is exactly where duplicate handling goes wrong. Both functions return their triplets in sorted order, so the lists can be compared directly. Run the full suite:
(venv) $ python -m pytestStep 8: Know when two pointers does not work
Knowing how the technique works is half the skill. Knowing when to use it is the other half. Work through four questions in order.
The questions are ordered so the more specific tools get the first chance. If a sorted list holds the value you want, binary search is enough, because one pointer does the job. A window of items belongs to sliding window.
Clues that point to two pointers
- The input is sorted, and you need a pair, a triple, or a closest value.
- The problem says “in place” or “O(1) extra space”.
- You need to compare the two ends, as in a palindrome.
- You need to remove or filter items from a list.
- You must merge two sorted sequences.
- It is a linked list, and you need the middle or a cycle.
When it does not work
| Situation | Why two pointers fails | Better tool |
|---|---|---|
| Pair sum on an unsorted list, and you need the original positions | Sorting changes the positions | A dictionary |
| Sum of a contiguous subarray that may contain negative numbers | A pointer cannot decide when to move | Prefix sum with a dictionary |
| Problems about a window of items | A window is a better fit | Sliding window |
| Finding one item in a sorted list | One pointer is enough | Binary search |
Does the technique always need sorted input? No. Reversing and palindrome checks work on unsorted data. Pair sum, removing duplicates and merging need sorted data. Ask whether your logic depends on order.
Sorting is also not free. If the input is not sorted and you sort it first, the total time is O(n log n), and the sort becomes the slowest part.
Two bugs that bite
The code for these bugs lives in its own module so the working toolkit stays clean. Save this as pitfalls.py:
"""Buggy versions of the pair sum, kept so tests can show how they fail."""
def pair_sum_less_equal(sorted_nums: list[int], target: int) -> list[int]:
"""Bug: the loop uses <= so an item can be paired with itself."""
left, right = 0, len(sorted_nums) - 1
while left <= right:
total = sorted_nums[left] + sorted_nums[right]
if total == target:
return [left, right]
if total < target:
left += 1
else:
right -= 1
return []
def pair_sum_stuck(
sorted_nums: list[int], target: int, max_steps: int = 1_000
) -> list[int]:
"""Bug: when the total equals the target, no pointer moves.
A real version of this bug loops forever. This one raises an error
after max_steps rounds so a test can catch it instead of hanging.
"""
left, right = 0, len(sorted_nums) - 1
steps = 0
while left < right:
steps += 1
if steps > max_steps:
raise RuntimeError("pointers stopped moving")
total = sorted_nums[left] + sorted_nums[right]
if total < target:
left += 1
elif total > target:
right -= 1
# Missing: the equal case. Nothing moves, so the loop repeats.
return []The first bug writes left <= right instead of left < right. When the pointers meet on the same item, that item gets paired with itself. The second bug forgets to move a pointer when the total equals the target. Every branch must either move a pointer or return. Save these checks as test_pitfalls.py:
import pytest
from pitfalls import pair_sum_less_equal, pair_sum_stuck
from two_pointers import pair_with_target_sum
def test_less_equal_pairs_an_item_with_itself() -> None:
# Only one 4 exists, so 4 + 4 = 8 is not a real answer.
assert pair_sum_less_equal([4], 8) == [0, 0]
assert pair_with_target_sum([4], 8) == []
def test_stuck_version_never_finishes_when_a_pair_exists() -> None:
with pytest.raises(RuntimeError, match="stopped moving"):
pair_sum_stuck([1, 3, 5, 8, 11], 13)
def test_stuck_version_looks_fine_when_there_is_no_pair() -> None:
# The bug hides until the first time the total equals the target.
assert pair_sum_stuck([1, 3, 5, 8, 11], 100) == []The last test is the sneaky one. The stuck version passes every case where no pair exists, so it can survive a lot of testing before the first matching input exposes it.
Edge cases to test every time
The tests in this tutorial return to the same short list, because pointer loops usually break at the edges:
- an empty list
- one item
- two items
- all items equal
- duplicate values
- negative numbers
- no valid answer
Also say clearly whether a function changes its input in place. reverse_in_place() and remove_duplicates() do, and three_sum() and merge_sorted() do not.
Practice problems
Three more problems use the same patterns. Try each one for a few minutes before you read the solution. Save the solutions as practice.py:
| Problem | Level | Pointer type |
|---|---|---|
| Is subsequence | Easy | Same direction |
| Squares of a sorted array | Easy | Opposite direction |
| Container with most water | Medium | Opposite direction |
Is subsequence
Check whether one string appears inside another in order, with gaps allowed. Hint: walk through the long string once, and move a pointer in the short string only when you find a match.
def is_subsequence(short: str, long: str) -> bool:
"""Check whether short appears in long in order, possibly with gaps."""
i = 0
for char in long:
if i < len(short) and char == short[i]:
i += 1
return i == len(short)The time is O(n), where n is the length of the long string, and the extra space is O(1). An empty short returns True, which is correct, because an empty string is a subsequence of anything.
Squares of a sorted array
Given a sorted list that can have negative numbers, return the squares in sorted order. Hint: the biggest square is at one of the two ends, because a large negative number has a large square. Fill the answer from the back.
def sorted_squares(sorted_nums: list[int]) -> list[int]:
"""Square every number in a sorted list and return the squares sorted."""
n = len(sorted_nums)
result = [0] * n
left, right = 0, n - 1
# The biggest square is at one of the two ends, so fill from the back.
for pos in range(n - 1, -1, -1):
if abs(sorted_nums[left]) > abs(sorted_nums[right]):
result[pos] = sorted_nums[left] ** 2
left += 1
else:
result[pos] = sorted_nums[right] ** 2
right -= 1
return resultThe time is O(n) and the extra space is O(n) for the output. Squaring everything and calling sort() would cost O(n log n), so two pointers is faster here, because the input is already sorted.
Container with most water
You get a list of heights, where each height is a vertical line. Pick two lines, and together with the x-axis they form a container. Find the most water a container can hold. Hint: the water depends on the shorter line and the distance between the lines, so start with the widest container and move the shorter line inward.
def max_area(heights: list[int]) -> int:
"""Return the most water that two vertical lines can hold."""
left, right = 0, len(heights) - 1
best = 0
while left < right:
height = min(heights[left], heights[right])
best = max(best, height * (right - left))
# The width only shrinks from here, so only a taller line can help.
# The shorter line limits the height, so it is the one to drop.
if heights[left] < heights[right]:
left += 1
else:
right -= 1
return bestWhy move the shorter line? The width shrinks on every step, so the only way to hold more water is to find a taller line. The shorter line limits the height, so keeping it can never improve the answer. The time is O(n) and the extra space is O(1), against O(n²) for the brute force.
Save these checks as test_practice.py. The random tests compare each function with a plain brute-force expression:
import random
import pytest
from practice import is_subsequence, max_area, sorted_squares
@pytest.mark.parametrize(
("short", "long", "expected"),
[
("ace", "abcde", True),
("aec", "abcde", False),
("", "abc", True),
("", "", True),
("a", "", False),
("abc", "abc", True),
("abcd", "abc", False),
],
)
def test_is_subsequence(short: str, long: str, expected: bool) -> None:
assert is_subsequence(short, long) is expected
def test_sorted_squares_example() -> None:
assert sorted_squares([-4, -1, 0, 3, 10]) == [0, 1, 9, 16, 100]
@pytest.mark.parametrize("nums", [[], [0], [-3], [-2, -1], [1, 2, 3], [-5, -3, -1]])
def test_sorted_squares_matches_square_then_sort(nums: list[int]) -> None:
assert sorted_squares(nums) == sorted(n * n for n in nums)
def test_sorted_squares_agrees_with_square_then_sort_on_random_input() -> None:
rng = random.Random(11)
for _ in range(500):
nums = sorted(rng.randint(-10, 10) for _ in range(rng.randint(0, 12)))
assert sorted_squares(nums) == sorted(n * n for n in nums)
def test_max_area_example() -> None:
assert max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49
@pytest.mark.parametrize(
("heights", "expected"),
[([], 0), ([5], 0), ([1, 1], 1), ([4, 3, 2, 1, 4], 16)],
)
def test_max_area_edge_cases(heights: list[int], expected: int) -> None:
assert max_area(heights) == expected
def test_max_area_agrees_with_brute_force_on_random_input() -> None:
rng = random.Random(5)
for _ in range(500):
heights = [rng.randint(0, 9) for _ in range(rng.randint(0, 12))]
expected = max(
(
min(heights[i], heights[j]) * (j - i)
for i in range(len(heights))
for j in range(i + 1, len(heights))
),
default=0,
)
assert max_area(heights) == expectedIf you want more, try the same ideas with empty lists, one item, and all zeros. The middle-of-a-linked-list problem from Step 6 completes the set of five.
Conclusion
You built a tested toolkit of two-pointers functions and measured why it matters: on 8,000 items, the nested-loop pair sum took about 2.2 seconds, and the two pointers version took under a millisecond. Along the way, you:
- Wrote opposite-direction solutions for pair sum, reverse and palindrome
- Wrote same-direction solutions for remove duplicates and merge
- Used fast and slow pointers to find the middle of a linked list
- Combined the pair-sum idea with a loop to solve three sum in O(n²)
- Checked the fast versions against brute force on thousands of random inputs
- Saw the two bugs that break pointer loops, and why unsorted input silently gives wrong answers
The key habit is a single question. When you see a nested loop, ask: “Can one comparison let me throw away an item for good?” If the answer is yes, two pointers may turn O(n²) into O(n).
The complete project is on GitHub, if you want to run the tests yourself.
A natural next step is the sliding window, which is a special case of two pointers where the pointers mark the start and end of a contiguous window and a running value is kept for it. Also, if you are searching a sorted list for one value, the standard library already has the tool: the bisect module finds insertion points with a binary search, which is O(log n).
Sources
- Python documentation: bisect describes binary search on sorted lists.
Leave a Reply