- Solve trapping rainwater using left/right max tracking
- Apply sliding window with frequency counters for substring problems
- Master minimum window substring with expand-contract strategy
- Handle duplicates with at-most-k constraint using comparison with k positions back
Advanced Two Pointers Problems
You've seen two pointers solve pairs, triplets, and linked list problems. Now let's tackle problems that seem impossible at first glance—and watch two pointers handle them elegantly.
Trapping Rainwater
Here's a classic problem: you have an array representing elevation heights [0,1,0,2,1,0,1,3,2,1,2,1]. How much rainwater gets trapped between the bars?
█
█ ██ █
█ ████████
0102101 3212 1
Water gets trapped in the valleys. At position 2 (height 0), water fills up to height 2 (limited by the 2 on the left and the 3 on the right), trapping 2 units.
The naive approach calculates the max height to the left and right for each position, then the water at that position is min(left_max, right_max) - height. That's O(n²) or O(n) with extra arrays.
Two pointers solves this in O(n) time with O(1) space:
def trap(heights):
if not heights:
return 0
left, right = 0, len(heights) - 1
left_max = right_max = 0
water = 0
while left < right:
if heights[left] < heights[right]:
# Water at left is limited by left_max
if heights[left] >= left_max:
left_max = heights[left]
else:
water += left_max - heights[left]
left += 1
else:
# Water at right is limited by right_max
if heights[right] >= right_max:
right_max = heights[right]
else:
water += right_max - heights[right]
right -= 1
return water
Why does this work? The key insight: water level at a position is limited by the minimum of the max heights on both sides. When we process the left pointer, we know heights[right] is at least as tall as heights[left], so the right side won't be the limiting factor. We can safely calculate water based on left_max.
For [0,1,0,2,1,0,1,3,2,1,2,1]:
left=0, right=11, left_max=0, right_max=0, water=0
heights[0]=0 < heights[11]=1
left_max=0, water+=0, left=1
left=1, right=11, left_max=0, right_max=0, water=0
heights[1]=1 < heights[11]=1
Actually equal, so go to else branch
right_max=1, water+=0, right=10
left=1, right=10, left_max=0, right_max=1, water=0
heights[1]=1 < heights[10]=2
left_max=1, water+=0, left=2
left=2, right=10, left_max=1, right_max=1, water=0
heights[2]=0 < heights[10]=2
water += 1-0 = 1, left=3
left=3, right=10, left_max=1, right_max=1, water=1
heights[3]=2 > heights[10]=2
Equal, else branch
right_max=2, water+=0, right=9
... continue until left meets right
Final water: 6
Longest Substring Without Repeating Characters
Find the length of the longest substring with no repeating characters. For "abcabcbb", it's "abc" (length 3).
Sliding window approach:
def longest_unique_substring(s):
if not s:
return 0
char_set = set()
left = 0
max_length = 0
for right in range(len(s)):
# Shrink window from left while we have a duplicate
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_length = max(max_length, right - left + 1)
return max_length
For "abcabcbb":
right=0 (a): char_set={a}, max_length=1
right=1 (b): char_set={a,b}, max_length=2
right=2 (c): char_set={a,b,c}, max_length=3
right=3 (a): 'a' in char_set!
Remove s[0]='a', left=1, char_set={b,c}
Add 'a', char_set={b,c,a}, max_length=3
right=4 (b): 'b' in char_set!
Remove s[1]='b', left=2, char_set={c,a}
Add 'b', char_set={c,a,b}, max_length=3
right=5 (c): 'c' in char_set!
Remove s[2]='c', left=3, char_set={a,b}
Add 'c', char_set={a,b,c}, max_length=3
right=6 (b): 'b' in char_set!
Remove s[3]='a', left=4, char_set={b,c}
Still 'b' in char_set!
Remove s[4]='b', left=5, char_set={c}
Add 'b', char_set={c,b}, max_length=3
right=7 (b): 'b' in char_set!
Remove s[5]='c', left=6, char_set={b}
Still 'b' in char_set!
Remove s[6]='b', left=7, char_set={}
Add 'b', char_set={b}, max_length=3
Result: 3
The right pointer explores new characters. When we hit a duplicate, the left pointer contracts until the duplicate is removed. The window between them is always a valid substring.
Minimum Window Substring
This is harder. Given string s and string t, find the smallest substring of s that contains all characters from t.
For s="ADOBECODEBANC" and t="ABC", the answer is "BANC".
This combines frequency counting with sliding window:
def min_window(s, t):
if not t or not s:
return ""
from collections import Counter
target_count = Counter(t)
window_count = Counter()
required = len(target_count) # Unique characters in t
formed = 0 # How many unique chars in window have desired frequency
left = 0
min_len = float('inf')
result = ""
for right in range(len(s)):
char = s[right]
window_count[char] += 1
# If this character's count matches target, increment formed
if char in target_count and window_count[char] == target_count[char]:
formed += 1
# Contract window from left while it's valid
while left <= right and formed == required:
# Update result if this window is smaller
if right - left + 1 < min_len:
min_len = right - left + 1
result = s[left:right + 1]
# Remove leftmost character from window
left_char = s[left]
window_count[left_char] -= 1
if left_char in target_count and window_count[left_char] < target_count[left_char]:
formed -= 1
left += 1
return result
For s="ADOBECODEBANC", t="ABC":
Expand right until we have all chars (A, B, C):
right gets to E in ADOBECODE
Window: "ADOBEC" contains all chars
Contract left while still valid:
Remove A: "DOBEC" - still has A? No, invalid
Expand right again:
Continue to B: "DOBECOB" - invalid still
Continue to A: "DOBECOBA" - valid again
Contract:
"OBECOBA", "BECOBA", "ECOBA", "COBA" - invalid
Continue expanding to N, C:
"ODEBANC" - valid
Contract:
"DEBANC", "EBANC", "BANC" - still valid (smallest so far)
"ANC" - invalid
Result: "BANC"
The technique: expand right to make the window valid, then contract left while maintaining validity, tracking the minimum.
3Sum Closest
Find three numbers that sum closest to a target. For nums=[−1,2,1,−4], target=1, the answer is 2 (−1+2+1=2).
This is 3Sum with a twist—instead of finding exact matches, track the closest sum:
def three_sum_closest(nums, target):
nums.sort()
closest = float('inf')
for i in range(len(nums) - 2):
left, right = i + 1, len(nums) - 1
while left < right:
current = nums[i] + nums[left] + nums[right]
# Update closest if this is closer
if abs(current - target) < abs(closest - target):
closest = current
# Move pointers based on comparison with target
if current < target:
left += 1
elif current > target:
right -= 1
else:
return current # Exact match
return closest
For [−1,2,1,−4], target=1:
Sort: [−4,−1,1,2]
i=0 (−4):
left=1 (−1), right=3 (2)
sum = −4+(−1)+2 = −3, |−3−1|=4, closest=−3
−3 < 1, left++
left=2 (1), right=3 (2)
sum = −4+1+2 = −1, |−1−1|=2, closest=−1
−1 < 1, left++
left=3, left>=right, done
i=1 (−1):
left=2 (1), right=3 (2)
sum = −1+1+2 = 2, |2−1|=1, closest=2 (better!)
2 > 1, right--
left=2, left>=right, done
Result: 2
Remove Duplicates, Allow Two
You have a sorted array. Remove duplicates so each element appears at most twice. For [1,1,1,2,2,3], the result is [1,1,2,2,3,_].
The trick: compare with the element two positions back. If they're the same, it means we already have two copies.
def remove_duplicates_ii(nums):
if len(nums) <= 2:
return len(nums)
slow = 2 # Position for next element
for fast in range(2, len(nums)):
# Only place if different from element 2 positions back
if nums[fast] != nums[slow - 2]:
nums[slow] = nums[fast]
slow += 1
return slow
For [1,1,1,2,2,3]:
slow=2, fast=2: nums[2]=1 == nums[0]=1? Yes, skip
slow=2, fast=3: nums[3]=2 != nums[1]=1, place
nums[2]=2, slow=3, array=[1,1,2,2,2,3]
slow=3, fast=4: nums[4]=2 == nums[2]=2? Yes, skip
slow=3, fast=5: nums[5]=3 != nums[3]=2, place
nums[3]=3, slow=4, array=[1,1,2,3,2,3]
Return 4, first 4 elements: [1,1,2,3]
Wait, that's wrong. Let me retrace:
Initial: [1,1,1,2,2,3]
slow=2
fast=2: nums[2]=1 vs nums[0]=1, equal, skip
fast=3: nums[3]=2 vs nums[1]=1, different
nums[2]=2, slow=3
Array: [1,1,2,2,2,3]
fast=4: nums[4]=2 vs nums[2]=2, equal, skip
fast=5: nums[5]=3 vs nums[3]=2, different
nums[3]=3, slow=4
Array: [1,1,2,3,2,3]
Return 4
First 4 elements: [1,1,2,3]
Hmm, we want [1,1,2,2,3]. Let me check the logic again. We're comparing nums[fast] with nums[slow-2]. At slow=3, we compare with nums[1]=1. At slow=4, we compare with nums[2]=2. So when fast=4 (value 2), we compare with nums[2]=2, which are equal, so we skip. That means we only keep two 2s. This is correct!
Actually reviewing: when slow=2 and we place the first 2, slow becomes 3. Now nums[0]=1, nums[1]=1, nums[2]=2. When fast=4 (another 2), we compare with nums[slow-2]=nums[1]=1, which is different, so we'd place it.
Let me trace more carefully:
[1,1,1,2,2,3], slow=2
fast=2: nums[2]=1, nums[slow-2]=nums[0]=1, equal, skip
fast=3: nums[3]=2, nums[slow-2]=nums[0]=1, different, place
nums[slow]=nums[2]=2, slow=3
[1,1,2,2,2,3]
fast=4: nums[4]=2, nums[slow-2]=nums[1]=1, different, place
nums[slow]=nums[3]=2, slow=4
[1,1,2,2,2,3]
fast=5: nums[5]=3, nums[slow-2]=nums[2]=2, different, place
nums[slow]=nums[4]=3, slow=5
[1,1,2,2,3,3]
Return 5: [1,1,2,2,3]
Perfect! By comparing with the element 2 positions back, we ensure we never have more than 2 duplicates.
The Pattern
Advanced two pointer problems often combine:
Sliding window for subarray/substring problems where you expand and contract the window.
Frequency tracking with hash maps or counters to handle character counts.
Greedy decisions about which pointer to move based on current state.
Invariant maintenance ensuring the window or pointer relationship stays valid.
The key is recognizing which variant applies and adapting the basic two-pointer template to the specific constraints.
These aren't fundamentally different from the simpler problems—they just require handling more complex state and making smarter decisions about pointer movement.