Two Pointers

Whenever you see “sorted array” plus “find a pair (or triplet) that sums to X”, or “do this in place without extra memory”, your brain should immediately reach for two pointers. Instead of nesting a loop inside a loop ($O(n^2)$), you walk the array with two indices that move toward each other or together, turning many brute-force problems into a single $O(n)$ pass.

What you’ll learn

• The two flavors of the pattern: opposite ends and same direction.
• A reusable template for each, written as plain Python functions.
• Why the pattern collapses $O(n^2)$ brute force into $O(n)$.
• Worked examples: sorted two-sum and a palindrome check.
• The interview cue that tells you “two pointers” before you’ve even finished reading the problem.

The pattern

Opposite ends — start one pointer at index 0 and the other at len(arr) - 1, then move them toward each other based on a comparison. Used for sorted-array pair sums, palindrome checks, and in-place reversal.

Same direction — a slow pointer and a fast pointer both start at the beginning; fast scans ahead and slow only advances when some condition is satisfied. Used for in-place partitioning, deduplication, and merging.

two_pointer_template.py

def opposite_ends_template(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current = arr[left] + arr[right]
        if current == target:
            return left, right
        elif current < target:
            left += 1      # sum too small -> need a bigger value
        else:
            right -= 1     # sum too big -> need a smaller value
    return -1, -1
 
 
def same_direction_template(arr):
    # slow marks the boundary of the "kept" region; fast scans ahead
    slow = 0
    for fast in range(len(arr)):
        if arr[fast] != 0:                       # example condition
            arr[slow], arr[fast] = arr[fast], arr[slow]
            slow += 1
    return arr
 
 
print(opposite_ends_template([1, 3, 4, 6, 8, 11, 15, 18], 14))
print(same_direction_template([0, 1, 0, 3, 12]))

The cue

You are looking at two pointers when…

• The input is sorted (or you are allowed to sort it) and the question asks for a pair, triple, or a value satisfying some relation. Sorting turns “search everything” into “walk inward from both ends”.
• The problem asks you to partition or compact in place with $O(1)$ extra space — a read pointer scanning and a write pointer marking where the next kept value goes.
• Two sequences must be traversed in step (merging, checking a subsequence).

The load-bearing property is monotonicity of the decision. At each step you must be able to prove that moving one specific pointer cannot discard the answer. On a sorted array, if the sum is too small, only moving lo right can increase it — moving hi left makes it strictly worse, so hi’s current position is safely eliminated.

Reach for something else when the array is unsorted and sorting would destroy required index information (use a hash map — that is exactly why LC 1 Two Sum is a hash-map problem while LC 167 is a two-pointer problem), or when the target subarray must be contiguous and the condition is not monotonic (prefix sums).

How it works

Both pointers only ever move forward (or toward each other) — neither ever backtracks. That’s what keeps the pattern linear: each index is visited a constant number of times across the whole run, so the total work is $O(n)$ instead of the $O(n^2)$ you’d get by checking every pair.

sketch Opposite-end pointers closing in on a sorted array p5.js Pause Restart

left starts at index 0, right at the last index. Each step compares nums[left] + nums[right] against the target and moves whichever pointer will change the sum in the right direction.

Worked example

Two Sum II (sorted input). Given a sorted array, return the 1-indexed positions of the two numbers that add up to target. Sorted input is the cue: no need for a hash set, opposite-end pointers do it in $O(1)$ extra space.

two_sum_sorted.py

def two_sum_sorted(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left + 1, right + 1]   # LeetCode wants 1-indexed
        elif total < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]
 
 
print(two_sum_sorted([2, 7, 11, 15], 9))     # expect [1, 2]
print(two_sum_sorted([1, 3, 4, 6, 8, 11, 15, 18], 14))

Valid Palindrome. Compare characters from both ends inward; as soon as a mismatch shows up, it isn’t a palindrome.

valid_palindrome.py

def is_palindrome(s):
    cleaned = [c.lower() for c in s if c.isalnum()]
    left, right = 0, len(cleaned) - 1
    while left < right:
        if cleaned[left] != cleaned[right]:
            return False
        left += 1
        right -= 1
    return True
 
 
print(is_palindrome("A man, a plan, a canal: Panama"))   # expect True
print(is_palindrome("race a car"))                        # expect False

3Sum reuses this exact pattern

3Sum fixes one number, then runs the opposite-ends two-pointer scan on the rest of the (sorted) array to find pairs that sum to -fixed. Sort once ($O(n \log n)$), then one two-pointer pass per fixed index — $O(n^2)$ total instead of the $O(n^3)$ brute force.

Time and space complexity

Approach	Time	Space
Brute-force pair check	$O(n^2)$	$O(1)$
Two pointers (sorted input)	$O(n)$	$O(1)$
Hash-set two-sum (unsorted input)	$O(n)$	$O(n)$

Two pointers beats the hash-set approach on space whenever the input is already sorted (or sortable) — that’s the trade you’re making.

When to use it

Cue in the problem	Pointer flavor
“sorted array, find a pair/triplet summing to X”	Opposite ends
“check if a string/array is a palindrome”	Opposite ends
“reverse in place”	Opposite ends
“remove/partition elements in place”	Same direction
“merge two sorted arrays in place, from the back”	Same direction (reversed)

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output — then paste the same code into leetcode.com.

LC 167 — Two Sum II, Input Array Is Sorted · Medium

Problem. Given a 1-indexed sorted array and a target, return the indices of the two numbers adding to target. There is exactly one solution, and you may not use the same element twice. Use only $O(1)$ extra space.

Constraints. 2 <= len(numbers) <= 3 * 10^4, sorted non-decreasing, -1000 <= numbers[i] <= 1000.

Examples. [2,7,11,15], target = 9 gives [1,2] · [2,3,4], target = 6 gives [1,3] · [-1,0], target = -1 gives [1,2]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Because the array is sorted, comparing the current pair’s sum to the target tells you which pointer to move. If the sum is too small, no pair using the current right and a smaller left can help, so left must advance — and symmetrically on the other side. Each step eliminates one index permanently.

Time $O(n)$. Space $O(1)$ — which is exactly why this differs from LC 1 Two Sum, where the input is unsorted and a hash map is needed at $O(n)$ space.

The 1-indexing is the detail most likely to cost a submission; the problem states it explicitly and it is easy to skim past.

Follow-ups you should expect: “What if the array were unsorted?” — sorting costs $O(n \log n)$ and destroys the original indices, so a hash map is better. “What if there were multiple answers?” — collect them and skip duplicates as in LC 15. “Three numbers (LC 15)?” — fix one and two-pointer the rest. “Closest sum rather than exact (LC 16)?” — same sweep, tracking the best difference seen.

LC 11 — Container With Most Water · Medium

Problem. Given height[i] as the height of a vertical line at position i, find two lines that together with the x-axis hold the most water. Return that maximum area.

Constraints. 2 <= len(height) <= 10^5, 0 <= height[i] <= 10^4.

Examples. [1,8,6,2,5,4,8,3,7] gives 49 · [1,1] gives 1 · [4,3,2,1,4] gives 16

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Start at the widest pair and close inward. The area is bounded by the shorter wall, so:

• Moving the taller wall inward reduces the width and cannot raise the height — the shorter wall still caps it. So the area can only get worse.
• Moving the shorter wall inward also reduces the width, but the new wall might be taller, so an improvement is at least possible.

Since moving the taller wall can never help, discarding it is safe — and that is the exchange argument that makes the greedy correct.

Time $O(n)$. Space $O(1)$.

[4,3,2,1,4] giving 16 is a good check: the answer uses the two outermost walls, so a solution that moves pointers wrongly and converges too fast misses it.

Follow-ups you should expect: “Prove the greedy is correct” — the argument above; it is the most likely question. “Trapping Rain Water (LC 42)?” — related but different: you accumulate water above every position, tracking left_max and right_max. “What if the walls had width?” — the area formula changes but the argument holds. “Brute force?” — $O(n^2)$ over all pairs; state it as the baseline.

LC 15 — 3Sum · Medium

Problem. Return all unique triplets [nums[i], nums[j], nums[k]] with distinct indices that sum to zero. The solution set must not contain duplicate triplets.

Constraints. 3 <= len(nums) <= 3000, -10^5 <= nums[i] <= 10^5.

Examples. [-1,0,1,2,-1,-4] gives [[-1,-1,2],[-1,0,1]] · [0,1,1] gives [] · [0,0,0] gives [[0,0,0]]

Why this test sorts the output

The problem accepts the triplets in any order, so the test sorts before comparing. Sorting the input is part of the algorithm regardless.

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Sorting does two jobs at once: it enables the two-pointer sweep, and it puts equal values next to each other so duplicates can be skipped by comparing neighbours.

Fix each index as the smallest member of the triplet, then find pairs summing to -nums[i] in the suffix.

Time $O(n^2)$ — $O(n \log n)$ to sort plus $O(n)$ per anchor. Space $O(1)$ beyond the output (ignoring the sort).

Deduplication happens in three places, and all three are needed:

1. Skip duplicate anchors — otherwise [-1,-1,2] is found twice.
2. Skip duplicate left values after a hit.
3. Skip duplicate right values after a hit.

[0,0,0,0] giving exactly one triplet is the minimal test of all three: without them you get several copies of [0,0,0].

The if nums[i] > 0: break is a genuine optimisation, not just a guard — once the smallest of three sorted values is positive, no triple can sum to zero.

Using a set of sorted tuples to deduplicate also works and is easier to get right, at $O(n^2)$ extra space. Worth mentioning; the skip version is what an interviewer usually wants.

Follow-ups you should expect: “4Sum (LC 18)?” — another nested loop, $O(n^3)$, with the same duplicate skipping at each level. “Closest to a target (LC 16)?” — track the best difference instead of collecting exact hits. “Count triplets rather than list them?” — same sweep, add counts. “Can you beat $O(n^2)$?” — not known; 3Sum is conjectured to require quadratic time.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

11 problems

6 easy4 medium1 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○26Remove Duplicates from Sorted ArrayeasyLeetCode Top Interview 150
• ○27Remove ElementeasyLeetCode Top Interview 150
• ○88Merge Sorted ArrayeasyLeetCode Top Interview 150
• ○125Valid PalindromeeasyConverge from both ends, skipping non-alphanumerics in place for $O(1)$ spaceNeetCode 150Blind 75LeetCode Top Interview 150
• ○283Move Zeroeseasy
• ○392Is SubsequenceeasyLeetCode Top Interview 150
• ○153SummediumSort, fix one index, then two-pointer the remainder -- and skip duplicates at every levelNeetCode 150Blind 75LeetCode Top Interview 150amazonmetamicrosoftapplebloomberg
• ○11Container With Most WatermediumAlways move the *shorter* wall inward; the taller one can never be the limiting factorNeetCode 150Blind 75LeetCode Top Interview 150amazonmetabloomberg
• ○80Remove Duplicates from Sorted Array IImediumLeetCode Top Interview 150
• ○167Two Sum II - Input Array Is SortedmediumThe template in its purest form -- sorted input, so move `left` up or `right` down by comparing the sum to the targetNeetCode 150LeetCode Top Interview 150
• ○42Trapping Rain WaterhardTrack `left_max` and `right_max` and always advance the smaller side -- $O(1)$ space, no stackNeetCode 150LeetCode Top Interview 150amazongooglemetabloomberg

Dry run

LC 167 with target = 9, nums = [2, 7, 11, 15]. Write it out this way on a whiteboard — the elimination column is the part interviewers want to hear.

Step	lo	hi	sum	vs target	move	why that move is safe
1	0 → 2	3 → 15	17	too big	hi--	15 is the largest value; paired with the smallest remaining it still overshoots, so 15 cannot be in any answer
2	0 → 2	2 → 11	13	too big	hi--	same argument eliminates 11
3	0 → 2	1 → 7	9	equal	stop	found

Three comparisons for a four-element array, versus six for the brute-force double loop. The gap widens fast: at $n = 1000$ it is 1,000 steps against 500,000.

Now the failure case — target = 100, same array:

Step	lo	hi	sum	move
1	0	3	17	lo++
2	1	3	22	lo++
3	2	3	26	lo++
4	3	3	—	lo < hi fails, loop ends

The pointers meet rather than cross, which is why the loop condition is lo < hi and not lo <= hi — with <= the final iteration would pair an element with itself, and “you may not use the same element twice” is almost always part of the problem statement.

The variant map

Four shapes, and recognising which one you have been handed is most of the work.

Variant	Pointer setup	What decides the move	Canonical problem
Converging from the ends	lo = 0, hi = n - 1	compare an aggregate against a target	167 Two Sum II · 11 Container With Most Water · 42 Trapping Rain Water
Fixed one, converge the rest	outer loop fixes i, then two pointers inside	the same comparison, one dimension down	15 3Sum · 16 3Sum Closest · 18 4Sum
Read / write compaction	both start at 0, write lags read	whether read’s value is kept	26 Remove Duplicates · 27 Remove Element · 283 Move Zeroes
Same direction, two sequences	one pointer per sequence	which sequence advances	392 Is Subsequence · 88 Merge Sorted Array

3Sum is 2Sum with a loop around it — and the dedup is the actual difficulty

Sort, then for each index i run the converging two-pointer scan on the remainder. That is $O(n^2)$, not $O(n^3)$.

The part that fails submissions is duplicate handling. Skip i when nums[i] == nums[i-1], and after recording a hit advance both inner pointers past their duplicates. A set of tuples also works and is easier to write under pressure, but say out loud that you are trading memory for simplicity — that acknowledgement is worth more than the cleaner solution.

Pitfalls

• Sorting when indices matter. LC 1 asks for indices in an unsorted array; sorting destroys them. That single difference is why LC 1 is a hash-map problem and LC 167 is a two-pointer problem, and interviewers ask both to see whether you notice.
• lo <= hi instead of lo < hi. With <= the last iteration pairs an element with itself. Almost every problem forbids that.
• Moving the wrong pointer in Container With Most Water. Move the shorter wall. Keeping it cannot help: width only shrinks from here, and the shorter wall already caps the height.
• Forgetting that the answer is a length, not an array, in compaction problems. LC 26 returns k; the slots past k hold leftover garbage the caller must ignore. Returning a sliced copy technically answers a different question.
• Assuming two pointers works on an unsorted array. Without sortedness there is no monotonic argument, and the pointers can walk past the answer. If you cannot state why a move is safe, the pattern does not apply.

Interview follow-ups

They ask	What they’re checking	The answer
“Why is this $O(n)$ and not $O(n^2)$?”	Whether you can justify the pattern	Each pointer only ever moves inward, so together they take at most $n$ steps total — every step eliminates at least one candidate permanently
“What if the array is not sorted?”	Whether you know the precondition	Sort first at $O(n \log n)$ — still better than $O(n^2)$ — unless indices must be preserved, in which case use a hash map
“Prove that moving hi left is safe”	Whether you understand or memorised	If sum > target, then nums[hi] paired with the smallest remaining value still overshoots, so nums[hi] appears in no valid pair and can be discarded
“Extend it to 4Sum”	Generalisation	Two nested loops around the same converging scan: $O(n^3)$. Beyond that, meet-in-the-middle with a hash map of pair sums beats more nesting
“What if duplicates are allowed in the output?”	Care with the dedup logic	Drop the skip conditions — but state that you are doing so deliberately, because it is the opposite of the usual requirement
“Do it without sorting, in $O(n)$”	Whether you reach for the right tool	Only possible with a hash map, and only for the pair case — 3Sum has no known $O(n)$ solution

Self-check

pch.quizTag Two pointers — self-check

1. Why is LC 1 (Two Sum) a hash-map problem while LC 167 (Two Sum II) is a two-pointer problem?

   A LC 167 is easier, so it gets the simpler technique B LC 167's array is already sorted, and LC 1 requires returning indices that sorting would destroy C Hash maps cannot be used on sorted arrays D Two pointers only works when the target is positive
   pch.quizShowAnswer

   B — LC 167's array is already sorted, and LC 1 requires returning indices that sorting would destroy — This pair is asked precisely to see whether you notice the difference. Two pointers needs sortedness for its safety argument; LC 1's array is unsorted AND wants original indices, so sorting is not available. That leaves the hash map.

2. In Container With Most Water, which wall do you move inward, and why?

   A The taller one, to look for something even taller B The shorter one, because the width can only shrink and the shorter wall already caps the height C Whichever is closer to the middle D Both, alternately
   pch.quizShowAnswer

   B — The shorter one, because the width can only shrink and the shorter wall already caps the height — Keeping the shorter wall cannot help: every remaining pair with it is narrower, and its height is still the binding limit. So it can be discarded safely. This is the exchange argument that makes the greedy correct rather than merely plausible.

3. The loop condition is `lo < hi` rather than `lo <= hi`. What breaks with `<=`?

   A Nothing — they are equivalent B The final iteration pairs an element with itself, which problems almost always forbid C It causes an index-out-of-range error D It makes the algorithm O(n²)
   pch.quizShowAnswer

   B — The final iteration pairs an element with itself, which problems almost always forbid — At lo == hi both pointers sit on the same element. 'You may not use the same element twice' is standard in these problems, so that iteration would produce an invalid answer.

4. What is the time complexity of the standard 3Sum solution, and where does it come from?

   A O(n³) — three nested loops B O(n²) — one outer loop around an O(n) converging scan, after an O(n log n) sort C O(n log n) — dominated by the sort D O(n) — with a hash map
   pch.quizShowAnswer

   B — O(n²) — one outer loop around an O(n) converging scan, after an O(n log n) sort — Sorting is O(n log n) and is dominated by the O(n²) main phase. There is no known O(n) solution for 3Sum, which is worth saying if asked to go faster.

5. LC 26 removes duplicates in place. What does it return, and what is in the array afterwards?

   A A new shorter array containing only the distinct values B The count k of distinct values; arr[:k] holds them and everything past k is leftover garbage C The number of duplicates removed D None — it mutates in place and returns nothing
   pch.quizShowAnswer

   B — The count k of distinct values; arr[:k] holds them and everything past k is leftover garbage — The write pointer's final position IS the answer. Nothing is truncated, because you cannot shrink an array in place — the contract is that the caller ignores everything from index k onward.

Recall card

• Cue — sorted input (or sortable) and a pair/triple relation; or in-place compaction with $O(1)$ space; or two sequences walked in step.
• Invariant — every pointer move must provably eliminate candidates. If you cannot state why, the pattern does not apply.
• Template — lo, hi = 0, n - 1; while lo < hi; compare an aggregate against the target and move the pointer whose current value is eliminated.
• Complexity — $O(n)$ after sorting, $O(1)$ space. 3Sum is $O(n^2)$; each extra fixed element costs another factor of $n$.
• Fails when — the array is unsorted and indices must be preserved (hash map), or the decision is not monotonic (prefix sums).

Recap

• Two pointers turns many $O(n^2)$ brute-force scans into a single $O(n)$ pass with $O(1)$ extra space.
• Opposite ends: start at both boundaries, move based on a comparison — sorted pair sums, palindromes, in-place reversal.
• Same direction: slow and fast both start at index 0, slow only advances when a condition holds — in-place partitioning and dedup.
• Cue: “sorted” + “pair/triplet sum” or “in place, no extra memory” almost always means two pointers.

Next: Sliding Window — stretching one of these two pointers into a window that expands and shrinks over a subarray.