Drag across the pointers. Click it, then use ← → to step and Space to play.
Two indexes, usually starting at opposite ends, move toward each other based on a comparison. It works because sorted order tells you which pointer to move: if the pair's sum is too small, the left value is too small for every partner still in range, so it can be ruled out and L moves right; if it is too big, R moves left. Every step rules out one element for good, so the pointers meet after at most n steps: O(n) time with O(1) space, instead of O(n²) for every pair.
FIG. 13 · The array sits in a type case like on page 1. L is the tag above the row and R the tag below it (in the examples, i is the black tag above). The red frame spans what is still possible; it turns dashed red just before a pointer moves, and the tiles left outside fade because they have been ruled out. Callout: A the input.
def two_sum_sorted(nums, target): # Two Sum II
L, R = 0, len(nums) - 1
while L < R:
s = nums[L] + nums[R]
if s < target:
L += 1 # need bigger
elif s > target:
R -= 1 # need smaller
else:
return [L, R]
return []
def is_palindrome(s):
L, R = 0, len(s) - 1
while L < R:
if s[L] != s[R]:
return False
L, R = L + 1, R - 1
return True
def maxArea(height): # LeetCode 11
L, R = 0, len(height) - 1
best = 0
while L < R:
area = (R - L) * min(height[L], height[R])
best = max(best, area)
if height[L] < height[R]:
L += 1 # the shorter wall limits the water
else:
R -= 1
return best
def threeSum(nums): # LeetCode 15
nums.sort()
res = []
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i - 1]:
continue # same first number: skip
L, R = i + 1, len(nums) - 1
while L < R:
s = nums[i] + nums[L] + nums[R]
if s < 0:
L += 1
elif s > 0:
R -= 1
else:
res.append([nums[i], nums[L], nums[R]])
L += 1
while L < R and nums[L] == nums[L - 1]:
L += 1 # skip duplicate second numbers
return res
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]. Water between two walls is width × the shorter wall. Start with the widest pair and always move the shorter wall inward, because moving the taller one can only lose width. Answer: 49. Trigger: "container with most water".
nums = [-1, 0, 1, 2, -1, -4]. Sort, fix the first number with i, then find pairs summing to −nums[i] with two pointers, skipping duplicates. Answer: [[-1, -1, 2], [-1, 0, 1]]. Trigger: "find a triplet".
| Problem | Time | Space | Why |
|---|---|---|---|
| Pair in a sorted array, palindrome, container | O(n) | O(1) | Each step moves one pointer inward and they never move back, so at most n steps. |
| Triplet (3Sum) | O(n²) | O(1) extra | One O(n) two-pointer pass for each of n first numbers, after an O(n log n) sort. |
| Brute force: every pair | O(n²) | O(1) | n(n − 1)/2 pairs. The pointers skip all but n of them, safely. |
| Hash map Two Sum (page 9) | O(n) | O(n) | Works on unsorted input but needs memory. Sorted input? Two pointers get O(1) space. |
With L and R at the ends of a sorted range, if nums[L] + nums[R] is too small, then nums[L] plus any value in the range is too small, because nums[R] is the largest of them. So nums[L] can't be in any answer, and dropping it loses nothing. The same argument, mirrored, drops nums[R] when the sum is too big. Every step removes one candidate with proof.
Both use L and R. A sliding window (page 12) has both pointers moving the same direction, keeping a contiguous stretch. Two pointers usually start at opposite ends and squeeze inward, using sorted order or symmetry to decide which side to give up.
Compare the ends; move the pointer the comparison rules out.
Pair position i with its mirror n − 1 − i and step both inward.
def two_sum_sorted(nums, target): # Two Sum II
L, R = 0, len(nums) - 1
while L < R:
s = nums[L] + nums[R]
if s < target:
L += 1 # need bigger
elif s > target:
R -= 1 # need smaller
else:
return [L, R]
return []
def is_palindrome(s):
L, R = 0, len(s) - 1
while L < R:
if s[L] != s[R]:
return False
L, R = L + 1, R - 1
return True