4 drills · 4 pattern exercises · 8 micro drills
Patterns used in this topic, with difficulty breakdown.
Remove duplicate values from a sorted list in-place and return how many unique values remain.
All 4 drills grouped by pattern. Each includes prompt, solution, and complexity.
In plain English: Pick two vertical lines to form a container. Find the pair that holds the most water.
Start with the widest container (both ends). The shorter line is the bottleneck — moving the taller one inward can only reduce width without increasing height. So always move the shorter pointer inward.
Prompt
Given n non-negative integers representing heights of vertical lines, find two lines that together with the x-axis form a container that holds the most water.
Solution
def max_area(height):
l, r = 0, len(height) - 1
best = 0
while l < r:
w = r - l
h = min(height[l], height[r])
best = max(best, w * h)
if height[l] < height[r]:
l += 1 # move shorter line inward
else:
r -= 1
return best
# Test: max_area([1,8,6,2,5,4,8,3,7]) == 49 (lines at indices 1,8)In plain English: Given a bar chart of heights, figure out how much rainwater gets trapped in the valleys between bars.
Water at any position = min(max_left, max_right) - height. Use two pointers: process from the side with the smaller max. That side's water level is determined since the other side is at least as tall.
Prompt
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Solution
def trap(height):
l, r = 0, len(height) - 1
left_max = right_max = 0
water = 0
while l < r:
# process from the shorter side: its water level is fully determined
# because the opposite side is at least as tall
if height[l] < height[r]:
left_max = max(left_max, height[l])
water += left_max - height[l] # gap between max seen and current bar
l += 1
else:
right_max = max(right_max, height[r])
water += right_max - height[r]
r -= 1
return water
# Test: trap([0,1,0,2,1,0,1,3,2,1,2,1]) == 6
# Test: trap([4,2,0,3,2,5]) == 9In plain English: Find all unique sets of three numbers in the array that add up to zero.
Sort the array, fix one element, then use two pointers on the remainder to find pairs summing to the negative of the fixed element. Skip duplicates at each level to avoid repeated triplets.
Prompt
Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that i != j != k and nums[i] + nums[j] + nums[k] == 0.
Solution
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue # skip duplicate fixed element
l, r = i + 1, len(nums) - 1
while l < r:
total = nums[i] + nums[l] + nums[r]
if total == 0:
result.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]:
l += 1 # skip duplicates
while l < r and nums[r] == nums[r-1]:
r -= 1 # skip duplicates
l += 1; r -= 1
elif total < 0:
l += 1
else:
r -= 1
return result
# Test: three_sum([-1,0,1,2,-1,-4]) == [[-1,-1,2],[-1,0,1]]
# Test: three_sum([0,0,0]) == [[0,0,0]]In plain English: Remove duplicate values from a sorted list in-place and return how many unique values remain.
Slow pointer marks the write position, fast pointer scans ahead. When fast finds a new value, write it at slow+1 and advance slow. The sorted order guarantees duplicates are adjacent.
Prompt
Given a sorted array nums, remove the duplicates in-place such that each element appears only once. Return the new length.
Solution
def remove_duplicates(nums):
if not nums:
return 0
slow = 0 # slow = next write position for a unique value
for fast in range(1, len(nums)): # fast scans ahead for new values
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
# Test: nums = [1,1,2]; remove_duplicates(nums) == 2; nums[:2] == [1,2]
# Test: nums = [0,0,1,1,1,2,2,3,3,4]
# remove_duplicates(nums) == 5; nums[:5] == [0,1,2,3,4]4 exercises: spot the signals, pick the method, avoid the trap.
Given n vertical lines, find two that form a container holding the most water.
Signals
Start at widest. Move the shorter line inward (can't do better keeping it). O(n).
Same logic. Moving the taller line can only decrease width without guaranteeing height increase.
Trap
Don't try all O(n²) pairs. The greedy proof: moving the taller side can never improve area.
Given n non-negative integers representing an elevation map, compute how much water it can trap.
Signals
Two pointers from ends. Process the side with smaller max. Water = max - height. O(n) time, O(1) space.
Monotonic stack tracking bars. Pop when current > stack top, compute trapped water. O(n) time, O(n) space.
Trap
The prefix/suffix max arrays work but use O(n) space. Two pointers achieve O(1) space.
Given array nums, find all unique triplets that sum to zero.
Signals
Sort. Fix i, two pointers on [i+1..n-1]. Skip duplicate values of i, l, r. O(n²).
For each pair, check if -(a+b) exists. Harder to deduplicate. O(n²).
Trap
Deduplication: skip i if nums[i] == nums[i-1]. Skip l if nums[l] == nums[l-1] after finding a triple.
Given a sorted array, remove duplicates in-place and return the new length.
Signals
Slow pointer writes unique values. Fast pointer scans. When different, advance slow and copy. O(n).
Same idea with a write index. Every unique element gets written to the next position.
Trap
Don't shift the entire array when removing — just overwrite with the slow pointer.
8 quick recall drills to reinforce this topic.
Greedy two-pointer moves the shorter wall inward. O(n) time, O(1) space.
l, r = 0, len(h)-1
mx = 0
while l < r:
mx = max(mx, min(h[l], h[r]) * (r - l))
if h[l] < h[r]: l += 1
else: r -= 1Greedy narrowing of left/right pointers maximizes area. Proof relies on the shorter-wall argument.
l, r = 0, len(h) - 1
best = 0
while l < r:
area = min(h[l], h[r]) * (r - l)
best = max(best, area)
if h[l] < h[r]: l += 1
else: r -= 1Two-pointer with running left/right max computes trapped water in O(n).
l, r = 0, len(h)-1
lm = rm = res = 0
while l < r:
if h[l] < h[r]:
lm = max(lm, h[l])
res += lm - h[l]
l += 1
else:
rm = max(rm, h[r])
res += rm - h[r]
r -= 1Converging pointers shrink the search space from both ends. Core of two-sum-sorted and palindrome.
l, r = 0, len(a) - 1
while l < r:
# process a[l], a[r]
l += 1; r -= 1Sort + fix first + two-pointer on remainder. Skip duplicates at all three levels.
a.sort()
for i in range(len(a)-2):
if i and a[i] == a[i-1]: continue
l, r = i+1, len(a)-1
while l < r:
s = a[i] + a[l] + a[r]
if s < 0: l += 1
elif s > 0: r -= 1
else:
res.append([a[i], a[l], a[r]])
l += 1
while l < r and a[l] == a[l-1]: l += 1Move-zeroes is remove-element followed by a fill. Classic two-pointer warm-up.
w = 0
for r in range(len(a)):
if a[r] != 0:
a[w] = a[r]
w += 1
while w < len(a):
a[w] = 0
w += 1Write-pointer compaction for sorted arrays. Returns new length.
w = 1
for i in range(1, len(a)):
if a[i] != a[i-1]:
a[w] = a[i]
w += 1
return wTwo-pointer write keeps unique elements in-place with O(1) space. Core array cleanup technique.
# Two-pointer write — keep unique in-place
w = 1
for r in range(1, len(a)):
if a[r] != a[r - 1]:
a[w] = a[r]
w += 1
# a[:w] has unique elements