Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 225 Ā· Arrays and Lists

Two Pointers

Learn the two pointers technique in Python: opposite ends, same direction and fast/slow pointers, with pair sum, remove elements, container with most water and 3Sum.

Many array problems have an obvious solution with two nested loops: check every pair. That works, but it costs O(n²), and with 100,000 items it is far too slow. The two pointers technique replaces the inner loop with a second index that moves in a smart, predictable way, so the whole scan finishes in O(n).

The trick is not magic. It works when you can say, after looking at the current pair, which pointer can safely move and why. In this lesson you will learn the three common shapes, solve four classic problems, and learn how to prove that moving a pointer never skips the answer.

The three shapes

TEXT
1. Opposite ends          2. Same direction          3. Fast and slow
   L ->           <- R       slow -> fast ->            slow -> (1 step)
   [ . . . . . . . . ]       [ . . . . . . . . ]        fast ---> (2 steps)
   move inward               read ahead, write behind   detect cycles, find middle
  • Opposite ends: one pointer at the start, one at the end, moving toward each other. Typical for sorted arrays, palindromes and "pair with a target" problems.
  • Same direction: a reader scans ahead while a writer marks the end of the processed prefix. You already used it to remove duplicates in place.
  • Fast and slow: two pointers move at different speeds. This is most useful on linked lists (finding the middle, detecting cycles), but also appears in arrays.

Pair sum in a sorted array

Problem. Given a sorted list nums and a number target, find two items that add up to target. Return their indexes, or None.

Brute force. Try every pair with two loops: O(n²) time, O(1) space.

Better. Put left at the start (smallest) and right at the end (largest) and look at the sum:

  • If the sum is too small, the only way to increase it is to use a bigger left value, so move left right.
  • If the sum is too big, move right left.
  • If it matches, done.

Why is it safe to discard the item we move past? Say the sum of nums[left] + nums[right] is too big. Every pairing of nums[right] with any left' >= left is at least as big, so nums[right] can never be part of an answer with the remaining left items. Throwing it away loses nothing.

TEXT
nums = [1, 3, 4, 6, 8, 11], target = 10
 L=1  R=11 -> 12 too big   -> R moves left
 L=1  R=8  ->  9 too small -> L moves right
 L=3  R=8  -> 11 too big   -> R moves left
 L=3  R=6  ->  9 too small -> L moves right
 L=4  R=6  -> 10 found!
Python Pair sum: brute force versus two pointers

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two-pointers loop makes at most n - 1 checks because each step moves one pointer closer. Both functions find the pair at indexes 2 and 3 (4 + 6), but the brute force needed 10 checks while two pointers needed 5. When several pairs match, any valid pair is a correct answer.

If the array is not sorted, opposite-end pointers do not work. Either sort first (O(n log n), but you lose original indexes) or use a hash table to solve Two Sum in O(n).

Valid palindrome

A palindrome reads the same forwards and backwards. Compare the outer characters, then move inward; mismatch means "no". This is the opposite-ends shape on a string. Skipping non-letters just means advancing a pointer without comparing.

Python Palindrome check ignoring punctuation

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

It uses O(1) extra space. The shortcut cleaned == cleaned[::-1] is shorter but builds two new strings of size n.

Remove elements in place (same direction)

Problem. Remove every occurrence of val from nums in place and return the new length. Order of the kept items must be preserved.

The reader scans every item. The writer only advances when we keep an item, so nums[:write] is always the answer so far. It is O(n) time, O(1) space.

Python Remove all occurrences of a value

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Container with most water

Problem. heights[i] is the height of a vertical line at position i. Pick two lines; together with the x-axis they form a container. Its area is min(height_a, height_b) * distance. Find the maximum area.

Brute force: try all pairs, O(n²).

Two pointers: start with the widest container (first and last lines). The area is limited by the shorter line. If you move the taller line inward, the width shrinks and the height can't get better (still limited by the shorter one), so the area can only drop. Moving the shorter line is the only move that might improve things. So always move the shorter side.

TEXT
heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
L=0 (1), R=8 (7): area = 1*8 = 8   -> move L (shorter)
L=1 (8), R=8 (7): area = 7*7 = 49  -> move R (shorter)
L=1 (8), R=7 (3): area = 3*6 = 18  -> move R ...
best found = 49
Python Container with most water

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Three sum

Problem. Find all unique triplets a + b + c == 0 in an array.

Brute force: three nested loops, O(n³), plus a set to remove duplicate triplets.

Better: sort the array (O(n log n)). Fix the first number nums[i], then solve a pair-sum problem on the rest with opposite-end pointers looking for -nums[i]. That is n times an O(n) scan: O(n²) overall. Skip repeated values for i, left and right to avoid duplicate triplets.

Python 3Sum with sorting and two pointers

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After finding a triplet both pointers must move, since keeping one fixed could only repeat the same triplet or find a worse sum. The extra while skips a repeated value on the left; because each triple is unique by its smallest value and then by its middle value, the right side doesn't need its own skip here (a repeated right would need a repeated left to still sum to zero).

Fast and slow pointers in an array

A quick taste: to find the middle of a list you can advance fast by 2 and slow by 1; when fast reaches the end, slow is at the middle. On a linked list, where you cannot jump to n // 2, this is the standard tool, so we use it in Linked List Techniques.

Sorted arrays as sets: union, intersection and merging in place

A sorted array is a set you can combine in one linear pass with two pointers, with no hash table. Walk both arrays, always advancing the pointer that holds the smaller value.

  • Union: emit the smaller value (skip repeats); on a tie emit it once and advance both.
  • Intersection: advance the smaller side; emit only on a tie.
  • Difference: emit values of a that never tie with b.

All three cost O(n + m) time. If one array is far shorter (m << n), binary-searching each of its values in the long one costs O(m log n), which can be smaller. For unsorted input, a Python set gives the same results in expected O(n + m) but loses the order.

Python Union, intersection and difference of sorted lists

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Merging two sorted arrays without extra space

Suppose the two sorted arrays must end up sorted across both, with the smaller half in a and the rest in b, and you may not allocate a third array. The gap method (a shell-sort idea) starts with gap = ceil((n + m) / 2), compares and swaps elements gap apart across the combined sequence, then halves the gap (rounding up) until it is 1. It runs in O((n + m) log(n + m)) time and O(1) space.

Python Gap method merge

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity

Problem Brute force Two pointers Extra space
Pair sum (sorted) O(n²) O(n) O(1)
Palindrome O(n) with reverse copy O(n) O(1)
Remove value O(n²) with deletes O(n) O(1)
Container with most water O(n²) O(n) O(1)
3Sum O(n³) O(n²) O(1) beyond sorting and output

When to use it, and mistakes

Think of two pointers when: the data is sorted, or you are looking for a pair/triple with a condition, or you need to partition/filter in place, or you compare both ends.

Common mistakes:

  • Using left <= right when the problem needs two different items (use <).
  • Applying opposite-ends pointers to an unsorted array.
  • Forgetting to skip duplicates in 3Sum and returning repeated triplets.
  • Moving both pointers when only one should move, which can skip the answer.
  • Returning the array instead of the new length for in-place removal problems.

Check your understanding

Quick check Ā· 5 questions

of 5 answered You scored / 5 Ā· perfect!

  1. 1. In pair sum on a sorted array, the current sum is smaller than the target. What should you do?

    A larger sum needs a larger left value, and since the array is sorted, moving left to the right is the only way to get one.
  2. 2. What is the time complexity of 3Sum using sorting plus two pointers?

    Sorting costs O(n log n), then each of the n choices for the first number runs an O(n) two-pointer scan.
  3. 3. In container with most water, which pointer should move?

    The area is limited by the shorter line. Moving the taller one only reduces the width and cannot raise the height limit, so only moving the shorter line can help.
  4. 4. Which situation does NOT suit opposite-end two pointers?

    Opposite-end pointers rely on order to decide which side to move. Unsorted arrays need sorting first or a hash table.
  5. 5. In the remove_value function, what does the write pointer represent?

    nums[:write] always holds the items kept so far, so write is both the next free slot and the final length.

Summary

  • Two pointers replaces a nested loop with two indexes that move in a justified way, usually giving O(n) instead of O(n²).
  • Opposite ends: sorted pair sum, palindromes, container with most water. Same direction: filtering and partitioning in place.
  • Always be able to explain why the pointer you move can never skip the answer.
  • 3Sum = sort + fix one number + pair sum; skip duplicates.
  • It needs order (sorted data) for the move decisions to be valid.

Next: Sliding Window