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."""
left, right = 0, len(nums) - 1
while left < right: # strict: never pair an element with itself
total = nums[left] + nums[right]
if total == target:
return left, right
if total < target:
left += 1 # need a bigger sum
else:
right -= 1 # need a smaller sum
return None
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."""
write = 0
for read in range(len(nums)):
if keep(nums[read]):
nums[write] = nums[read] # write never overtakes read, so this is safe
write += 1
return write
The in-place filter. write <= read always holds, so the write can never clobber an element that has not been read yet.
def triplets(nums: list[int], target: int) -> list[list[int]]:
"""Reduce a 3-sum to n independent 2-sums."""
nums.sort()
out: list[list[int]] = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # skip duplicate anchors
left, right = i + 1, len(nums) - 1
# ... Template A on nums[left:right+1] for target - nums[i]
return out
k-sum is a for loop wrapped around (k-1)-sum. 3Sum is O(n²), 4Sum is O(n³).
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)
"""
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return left + 1, right + 1
if total < target:
left += 1 # numbers[left] is too small even with the largest partner
else:
right -= 1 # numbers[right] is too large even with the smallest partner
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) |
[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
write = 1 # nums[0] is always kept
for read in range(1, len(nums)):
# nums[write - 1] is the last value we decided to keep.
if nums[read] != nums[write - 1]:
nums[write] = nums[read]
write += 1
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 |
def remove_duplicates_at_most_twice(nums: list[int]) -> int:
"""Same idea, but each value may survive twice."""
write = 0
for value in nums:
# Keep it unless the last two kept values are already this value.
if write < 2 or value != nums[write - 2]:
nums[write] = value
write += 1
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()
n = len(nums)
triplets: list[list[int]] = []
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:
break
# Dedup 1: an anchor value already used produces the same triplets.
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, n - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
triplets.append([nums[i], nums[left], nums[right]])
left += 1
right -= 1
# Dedup 2 and 3: slide past repeats of the values just used.
while left < right and nums[left] == nums[left - 1]:
left += 1
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.
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
"""
left, right = 0, len(height) - 1
best = 0
while left < right:
span = right - left
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
else:
right -= 1
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 |
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.