Sorting gives you a direction. Two pointers converging from the ends turn that direction into an O(n) search over all n² pairs.
The sliding window walks two indices forward together. Two pointers, in the classic sense, sends them toward each other from opposite ends. Each step throws away a whole family of candidate pairs at once, which is why a doubly-nested loop collapses into a single pass.
| Signal | What it looks like |
|---|---|
| Sortedness | The array is given sorted, or the answer does not depend on order so you may sort it yourself. |
| A pairwise relation | “two numbers summing to…”, “the widest pair”, “closest to a target”. |
| Space pressure | “in place”, “O(1) extra memory”, “do not allocate a new array”. |
| Palindromes | Anything comparing a string to itself reversed is the same converging motion. |
left at index 0 and right at index n-1. Evaluate the pair. Because the array is sorted, the comparison tells you which pointer cannot possibly be part of the answer with any remaining partner, so you move that one inward and never look at it again. Each step eliminates an entire row or column of the n×n pair grid.This is the proof to have ready, because it is the only interesting thing to say about the pattern.
nums[left] + nums[right] < target. Since the array is sorted, nums[right] is the largest value still available. So nums[left] paired with anything left in the range gives a sum no bigger than the one just computed, which is already too small. Therefore nums[left] is in no solution, and dropping it loses nothing. The symmetric argument covers the too-large case.Each iteration moves exactly one pointer inward by one, and the pointers start n-1 apart, so the loop runs at most n-1 times. O(n) after the sort.
def converge(nums: list[int], target: int) -> tuple[int, int] | None:
"""Find a pair in a sorted array summing to target."""
# 0: first index. len(nums) - 1: last index, since indices start at 0.
left, right = 0, len(nums) - 1
# Invariant: no pair that uses an index outside left..right can sum to target.
while left < right: # strict: never pair an element with itself
total = nums[left] + nums[right]
if total == target:
return left, right
if total < target:
# +1: nums[left] is too small even with the biggest partner. Drop it.
left += 1 # need a bigger sum
else:
# -1: nums[right] is too big even with the smallest partner. Drop it.
right -= 1 # need a smaller sum
return None # the pointers met: no pair exists
Use left < right, not <=, whenever the two pointers must select two different elements.
def compact(nums: list[int]) -> int:
"""Filter in place. Returns the length of the kept prefix."""
# keep(x): placeholder test that says "this value stays".
# Remove Duplicates: keep x if it differs from the last value kept.
write = 0 # 0: nothing kept yet. Next kept goes in slot 0
# read: index of the value being judged.
# Invariant: nums[0..write-1] holds every kept value from nums[0..read-1].
for read in range(len(nums)):
if keep(nums[read]):
nums[write] = nums[read] # write never overtakes read, so this is safe
write += 1 # +1: the kept prefix grew by one slot
return write # write = count of kept values
The in-place filter. write <= read always holds, so the write can never clobber an element that has not been read yet.
Reading the figure. Green cells are the kept prefix, nums[0..write-1]. Amber is the value being read. Red is a value that is skipped. Grey cells past write hold leftovers that no longer matter.
def triplets(nums: list[int], target: int) -> list[list[int]]:
"""Reduce a 3-sum to n independent 2-sums."""
nums.sort() # sorted order is what lets Template A work
out: list[list[int]] = []
# i: index of the anchor. - 2: leave room for two partners after i.
for i in range(len(nums) - 2):
# i > 0: slot 0 has no left neighbour to compare. i - 1: the previous anchor.
if i > 0 and nums[i] == nums[i - 1]:
continue # skip duplicate anchors
# i + 1: partners come after the anchor. len(nums) - 1: the last index.
left, right = i + 1, len(nums) - 1
# ... Template A on nums[left:right+1] for target - nums[i]
# (right+1 because a slice end is exclusive, so right stays included)
return out
k-sum is a for loop wrapped around (k-1)-sum. 3Sum is O(n²), 4Sum is O(n³).
Reading the figure. Violet is the fixed anchor i. Amber cells are left and right. Blue cells are still in range. Red is an anchor skipped because it repeats the one before.
left <= right when you need two distinct elements. It lets an element pair with itself.nums.sort() is in place. Mention it, or use sorted(nums).Given a 1-indexed array numbers sorted in non-decreasing order, find the two numbers that add up to target and return their 1-based indices. Exactly one solution exists, and you may not use an element twice. Extra space must be O(1).
def two_sum_sorted(numbers: list[int], target: int) -> tuple[int, int]:
"""Indices of the two values in a sorted array that sum to target.
Args:
numbers: Non-decreasing integers.
target: The required sum.
Returns:
The 1-based indices (i, j) with i < j and numbers[i-1] + numbers[j-1] == target.
Raises:
ValueError: If no such pair exists.
Example:
>>> two_sum_sorted([2, 7, 11, 15], 9)
(1, 2)
"""
# 0: first index. len(numbers) - 1: last index, since indices start at 0.
left, right = 0, len(numbers) - 1
# Invariant: the answer pair, if any, lies inside left..right.
while left < right: # strict: an element cannot pair with itself
total = numbers[left] + numbers[right]
if total == target:
# + 1: the problem wants 1-based indices, Python uses 0-based.
return left + 1, right + 1
if total < target:
left += 1 # numbers[left] is too small even with the largest partner
else:
# numbers[right] is too large even with the smallest partner.
right -= 1
raise ValueError("no pair sums to target")
numbers = [2, 7, 11, 15], target = 18:
| left | right | sum | action |
|---|---|---|---|
| 0 | 3 | 17 | too small, left++ |
| 1 | 3 | 22 | too large, right-- |
| 1 | 2 | 18 | match, return (2, 3) |
Reading the figure. Amber cells are the two pointers. Blue cells are still in range. Red cells are dropped, since no remaining partner can work with them. Green is the answer pair.
[3, 3] with target = 6: works, and the two pointers land on different indices.None that a caller may not check.Given a sorted array nums, remove duplicates in place so each value appears once, keeping the relative order. Return the number of unique elements k. The first k slots of nums must hold the result; what follows does not matter.
read scans every element. write marks where the next kept element goes. Because duplicates are removed, write can only fall behind read, never overtake it, so writing is always safe.def remove_duplicates(nums: list[int]) -> int:
"""Compact a sorted list in place so each value appears once.
Args:
nums: Sorted integers. Mutated in place.
Returns:
k, the number of unique values. nums[:k] holds them in order.
Example:
>>> data = [0, 0, 1, 1, 1, 2, 2, 3]
>>> k = remove_duplicates(data)
>>> (k, data[:k])
(4, [0, 1, 2, 3])
"""
if not nums:
return 0 # 0: an empty list has no unique values
write = 1 # nums[0] is always kept, so the next slot is 1
# read: index of the value being judged. Start at 1: slot 0 is already kept.
# Invariant: nums[0..write-1] are the unique values of nums[0..read-1].
for read in range(1, len(nums)):
# nums[write - 1] is the last value we decided to keep.
# Sorted input means a new value only has to differ from that one.
if nums[read] != nums[write - 1]:
nums[write] = nums[read] # copy the new value into the next free slot
write += 1 # +1: the kept prefix grew by one
return write
nums[write - 1] and not nums[read - 1]Both work for this problem, because sorted duplicates are adjacent and the prefix mirrors the source. But nums[write - 1] is the honest expression of the intent: is this different from the last thing I kept. That version generalises without change to the common follow-up, allow each value at most twice, where you compare against nums[write - 2]. The read - 1 version does not generalise.
nums = [1, 1, 2]:
| read | nums[read] | nums[write-1] | action | write |
|---|---|---|---|---|
| 1 | 1 | 1 | equal, skip | 1 |
| 2 | 2 | 1 | write nums[1] = 2 | 2 |
Reading the figure. Green cells are the kept prefix. Amber is the value being copied. Red is a skipped duplicate. Grey cells are not kept yet or are leftovers.
def remove_duplicates_at_most_twice(nums: list[int]) -> int:
"""Same idea, but each value may survive twice."""
write = 0 # 0: nothing kept yet. Next kept goes in slot 0
# value: the item being judged.
# Invariant: nums[0..write-1] holds each value seen so far, at most twice.
for value in nums:
# Keep it unless the last two kept values are already this value.
# write < 2: fewer than 2 kept, so no value can have 2 copies yet.
# write - 2: two slots back. Sorted input means a match there also
# matches the slot in between. So value would be a third copy.
if write < 2 or value != nums[write - 2]:
nums[write] = value
write += 1 # +1: the kept prefix grew by one
return write
One changed constant. This is why the write - 1 framing is worth the habit.
0.1.write never passes read, so writing into the prefix cannot destroy data I still need to read.”Given an array nums, return all unique triplets [a, b, c] with a + b + c == 0. The result must not contain duplicate triplets.
nums[i], then the problem becomes: find pairs in nums[i+1:] summing to -nums[i]. That is Two Sum II.left and repeated right values.def three_sum(nums: list[int]) -> list[list[int]]:
"""All unique triplets from nums that sum to zero.
Args:
nums: Integers, in any order. Sorted in place as a side effect.
Returns:
A list of triplets, each sorted ascending, with no duplicates.
Example:
>>> three_sum([-1, 0, 1, 2, -1, -4])
[[-1, -1, 2], [-1, 0, 1]]
"""
nums.sort() # sorted order makes the two-pointer scan valid
n = len(nums)
triplets: list[list[int]] = []
# i: index of the anchor. n - 2: leave room for two partners after i.
for i in range(n - 2):
# Sorted, so once the anchor is positive the three smallest remaining
# values are all positive and no triplet can reach zero.
if nums[i] > 0: # 0: the target sum
break
# Dedup 1: an anchor value already used produces the same triplets.
# i > 0: slot 0 has no earlier anchor. i - 1: the previous anchor.
if i > 0 and nums[i] == nums[i - 1]:
continue
# i + 1: partners sit after the anchor. n - 1: the last index.
left, right = i + 1, n - 1
# Invariant: every new triplet for this anchor uses partners in left..right.
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0: # 0: target. Too small, so raise the low end
left += 1
elif total > 0: # too big, so lower the high end
right -= 1
else:
triplets.append([nums[i], nums[left], nums[right]])
left += 1 # +1: step past the low partner just used
right -= 1 # -1: step past the high partner just used
# Dedup 2 and 3: slide past repeats of the values just used.
# left - 1: the value just used. Skip while it repeats.
while left < right and nums[left] == nums[left - 1]:
left += 1
# right + 1: the value just used. Skip while it repeats.
while left < right and nums[right] == nums[right + 1]:
right -= 1
return triplets
nums = [-2, 0, 0, 2, 2] after sorting. With anchor -2 at i = 0, the pointers find (0, 2) and record [-2, 0, 2]. Both pointers move, landing on the second 0 and the second 2, which are repeats, so both dedup loops advance past them and the pointers cross. Without those loops the same triplet is recorded twice.
Reading the figure. Violet is the anchor i. Amber cells are left and right. Blue cells are still in range. Red is a repeat that the skip loop steps over.
set of sorted tuples also produces the right answer and is easier to write under pressure. It costs extra memory and hashing, and it hides the fact that you understand where the duplicates come from. Write the explicit skips if you can; mention the set as the fallback you would use if short on time.The outer loop runs n times, each inner converge is O(n). Output space is not counted; the sort is in place.
range(n - 2) is empty, returns [].[0, 0, 0, 0]: returns exactly [[0, 0, 0]]. A good test of the dedup logic.[].nums[i] > 0 break is an optimisation, not a correctness fix. Say which it is.height[i] is the height of a vertical line at position i. Pick two lines so that the container they form with the x-axis holds the most water. Return that maximum area. The area for a pair is (j - i) * min(height[i], height[j]).
def max_area(height: list[int]) -> int:
"""Largest area of water trapped between two vertical lines.
Args:
height: Non-negative line heights, indexed by position.
Returns:
The maximum area. 0 if fewer than two lines.
Example:
>>> max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])
49
"""
# 0: leftmost line. len(height) - 1: rightmost line. Widest pair first.
left, right = 0, len(height) - 1
best = 0 # 0: no container measured yet
# Invariant: every pair with an end outside left..right is no better than best.
while left < right:
span = right - left # width between the two lines
# The shorter line caps the water level.
best = max(best, span * min(height[left], height[right]))
# Only moving the shorter line can raise the min, so only that move
# has any chance of beating the current area.
if height[left] < height[right]:
left += 1 # +1: give up the short left line
else:
right -= 1 # -1: give up the short right line
return best
height[left] < height[right]. Consider any pair (left, j) with j < right. Its width is smaller than right - left, and its height is at most height[left], which is the current minimum. So its area is strictly less than the area just computed. Every remaining pair that uses left is therefore dominated, and discarding left cannot lose the optimum. That is exactly the exchange argument from the top of the page, with width in place of sortedness.height = [1, 8, 6, 2, 5, 4, 8, 3, 7]:
| left | right | span | min height | area | best |
|---|---|---|---|---|---|
| 0 | 8 | 8 | 1 | 8 | 8 |
| 1 | 8 | 7 | 7 | 49 | 49 |
| 1 | 7 | 6 | 3 | 18 | 49 |
| 1 | 6 | 5 | 8 | 40 | 49 |
Reading the figure. Each chart is one step. Amber bars are left and right. Blue bars are still in range. The shaded box is the water, as wide as the span and as tall as the shorter line. Green marks the best area.
The scan continues but never beats 49.
0.left < right whenever the two picks must be distinct elements.Pattern 3, Fast and Slow Pointers, keeps two pointers moving in the same direction but at different speeds. That difference in speed is what detects a cycle in a structure you cannot index into.