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 00 and the other at len(arr) - 1len(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 slowslow pointer and a fastfast pointer both start at the beginning; fastfast scans ahead and slowslow 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]))

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]))

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

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 targettarget. 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))

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

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

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 targettarget, return the indices of the two numbers adding to targettarget. 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^42 <= len(numbers) <= 3 * 10^4, sorted non-decreasing, -1000 <= numbers[i] <= 1000-1000 <= numbers[i] <= 1000.

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

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 rightright and a smaller leftleft can help, so leftleft 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]height[i] as the height of a vertical line at position ii, find two lines that together with the x-axis hold the most water. Return that maximum area.

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

Examples. [1,8,6,2,5,4,8,3,7][1,8,6,2,5,4,8,3,7] gives 4949 · [1,1][1,1] gives 11 · [4,3,2,1,4][4,3,2,1,4] gives 1616

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][4,3,2,1,4] giving 1616 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_maxleft_max and right_maxright_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]][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) <= 30003 <= len(nums) <= 3000, -10^5 <= nums[i] <= 10^5-10^5 <= nums[i] <= 10^5.

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

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]-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:

Skip duplicate anchors — otherwise [-1,-1,2][-1,-1,2] is found twice.
Skip duplicate leftleft values after a hit.
Skip duplicate rightright values after a hit.

[0,0,0,0][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][0,0,0].

The if nums[i] > 0: breakif 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 setset 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

#	Problem	Difficulty	The twist
167	Two Sum II - Input Array Is Sorted	Medium	The template in its purest form — sorted input, so move `leftleft` up or `rightright` down by comparing the sum to the target
125	Valid Palindrome	Easy	Converge from both ends, skipping non-alphanumerics in place for $O(1)$ space
15	3Sum	Medium	Sort, fix one index, then two-pointer the remainder — and skip duplicates at every level
11	Container With Most Water	Medium	Always move the shorter wall inward; the taller one can never be the limiting factor
42	Trapping Rain Water	Hard	Track `left_maxleft_max` and `right_maxright_max` and always advance the smaller side — $O(1)$ space, no stack

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: slowslow and fastfast both start at index 0, slowslow 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.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Two Pointers

What you’ll learn

The pattern

How it works

Worked example

Time and space complexity

When to use it

Practice — real LeetCode problems

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

LC 11 — Container With Most Water · Medium

LC 15 — 3Sum · Medium

LeetCode problem set

Recap

Was this page helpful?