TWO POINTER PATTERN
DSA Interview Reference Guide
Problems Covered
01 Move Zeroes — Easy
02 Two Sum II — Medium
03 3Sum — Medium
04 Sort Colors — Medium
05 Container With Most Water — Medium
06 Trapping Rain Water — Hard
Arrays · O(n) to O(n²) · In-place · Sorting prerequisite
Open this doc after 5 years — it will still make instant sense.
The Master Rule
What is Two Pointer?
Two Pointer means using two variables (left and right, or fast and slow) to scan an array — instead of
nested loops. This reduces O(n²) to O(n).
Two Flavours — Memorise These Forever
SAME DIRECTION (→ →) OPPOSITE ENDS (→ ←)
Both pointers move LEFT → RIGHT Left pointer starts at 0 (smallest)
One is FAST (scanner), one is SLOW (placer) Right pointer starts at n-1 (largest)
Array does NOT need to be sorted Array MUST be sorted first
Used for: Move Zeros Used for: Two Sum, 3Sum, Container, Rain Water
The Two-Second Mental Check
Q: Does the answer depend on pairs/triplets from a sorted array?
→ YES → Sort first, then squeeze from both ends.
→ NO → Both pointers go same direction (fast/slow).
01 Move Zeroes [Easy]
Companies: Amazon · Google · Swiggy
What the problem wants
Given an array, move all 0s to the end while keeping non-zero elements in their original order. Do it in-place (no
extra array).
Pointer Setup
left → SLOW — tracks the next empty slot for a non-zero number
right → FAST — scans every element in the array one by one
Algorithm — Step by Step
Both pointers start at index 0. right moves every iteration. left only moves when it places a non-zero number.
Condition Action
arr[right] != 0 swap(left, right) then left++
arr[right] == 0 do nothing (skip it)
always right++
Dry Run → [0, 1, 0, 3, 12]
right=0: arr[0]=0 → skip. right++
right=1: arr[1]=1 → swap(0,1)=[1,0,0,3,12] left=1 right++
right=2: arr[2]=0 → skip. right++
right=3: arr[3]=3 → swap(1,3)=[1,3,0,0,12] left=2 right++
right=4: arr[4]=12 → swap(2,4)=[1,3,12,0,0] left=3 right++
Result: [1, 3, 12, 0, 0] ✔
Common Mistakes ✘
✘ Moving left++ even when arr[right]==0 → left points to wrong slot
✘ Forgetting right++ → infinite loop
✘ Checking left<right instead of right<n → stops too early
ONE-LINE RECALL right scans · left places · swap on non-zero · always right++
Time Complexity Space Complexity
O(n) — one pass O(1) — in-place, no extra array
02 Two Sum II [Medium]
Companies: Amazon · Google · Goldman Sachs
What the problem wants
Given a SORTED array and a target, find two numbers that add up to target. Return their indices (1-indexed).
Exactly one solution guaranteed.
Why sorting matters
In a sorted array, if your sum is TOO BIG, you must make the right pointer smaller (move left). If TOO
SMALL, you must make the left pointer bigger (move right). This is the entire logic.
Pointer Setup
left → Starts at index 0 — points at the SMALLEST number
right ← Starts at index n-1 — points at the LARGEST number
Algorithm — Step by Step
Squeeze the two pointers toward each other based on the sum:
Condition Action
sum == target FOUND → return [left+1, right+1]
sum > target right-- (sum is too big, shrink right side)
sum < target left++ (sum is too small, grow left side)
Dry Run → [2, 7, 11, 15], target=9
left=0, right=3: 2+15=17 >9 → right--
left=0, right=2: 2+11=13 >9 → right--
left=0, right=1: 2+7=9 ==9 → return [1, 2] ✔
Common Mistakes ✘
✘ Using left <= right instead of left < right → same element added to itself
✘ Forgetting the array must already be sorted → logic breaks on unsorted input
✘ Moving both pointers when sum matches → not needed, one solution exists
ONE-LINE RECALL Sort (already done) · squeeze · too big→right-- · too small→left++
Time Complexity Space Complexity
O(n) — one pass (sorting already O(1) — only two pointers
done)
03 3Sum [Medium]
Companies: Facebook · Microsoft · Morgan Stanley
What the problem wants
Find all unique triplets in the array that sum to zero. No duplicate triplets in the output.
Big Idea → 3Sum = Two Sum II inside a for loop
Fix one number using index i. Then run Two Sum II on the remaining sub-array using j and k. Repeat
for every valid i.
Pointer Setup
i → Fixed anchor (for loop: 0 to n-3). The number we pin.
j → Left pointer — starts at i+1 each round
k ← Right pointer — starts at n-1 each round
Setup Before Loop
sort(nums) // MANDATORY — enables two pointer logic
for i = 0 to n-3:
j = i + 1
k = n - 1
// run while j < k
Decision Table (inside while j < k)
Condition Action
sum == 0 save [i,j,k] · j++ · k-- · skip duplicates for j and k
sum > 0 k-- (too big, shrink right side)
sum < 0 j++ (too small, grow left side)
⚠ Duplicate Skipping — The Hardest Part
Skip duplicate i (before running inner loop):
if (i > 0 && nums[i] == nums[i-1]) continue;
Skip duplicate j (after j++ when sum==0):
while (j < k && nums[j] == nums[j-1]) j++;
Skip duplicate k (after k-- when sum==0):
while (j < k && nums[k] == nums[k+1]) k--;
Rule: Always skip AFTER you move j++/k-- first. Skipping before means you miss a valid pair.
Dry Run → [-1, 0, 1, 2, -1, -4] (sorted: [-4,-1,-1,0,1,2])
i=0 (val=-4): j=1,k=5: -4+-1+2=-3<0 j++ ...no match
i=1 (val=-1): j=2,k=5: -1+-1+2=0 ✔ save [-1,-1,2], j++,k--
j=3,k=4: -1+0+1=0 ✔ save [-1,0,1], j++,k--
i=2 (val=-1): same as i=1 → SKIP (duplicate)
i=3 (val=0): j=4,k=5: 0+1+2=3>0 k-- → j meets k, stop
Result: [[-1,-1,2],[-1,0,1]] ✔
Common Mistakes ✘
✘ i loop goes to n-1 → j and k have no room (need at least 2 elements after i)
✘ Skipping duplicates BEFORE j++/k-- → valid pair never seen
✘ Forgetting i>0 guard when skipping duplicate i → ArrayIndexOutOfBounds at i=0
✘ Not sorting first → everything is wrong
ONE-LINE RECALL Sort · fix i · TwoSum on rest · skip dupes after moving
Time Complexity Space Complexity
O(n²) — outer loop O(n) × inner O(1) extra (output list not
O(n) counted)
04 Sort Colors [Medium]
Companies: Microsoft · Flipkart · Adobe
What the problem wants
Given an array with only 0s, 1s, and 2s, sort it in-place in a single pass. No library sort allowed. This is the Dutch
National Flag problem.
Big Idea → Three Pointers divide the array into zones
low tracks where next 0 goes. high tracks where next 2 goes. mid scans everything.
Pointer Setup
low → Left boundary — everything before low is 0
mid → Scanner — current element being examined
high ← Right boundary — everything after high is 2
Array Zones (visualise this every time)
[ 0s | 1s | unsorted | 2s ]
^low ^mid ^high
Decision Table (while mid <= high)
Condition Action
arr[mid] == 0 swap(low, mid) · low++ · mid++
arr[mid] == 1 mid++ (1 is in the right zone, just advance)
arr[mid] == 2 swap(mid, high) · high-- (do NOT mid++)
Why no mid++ when swapping with high?
When you swap arr[mid] with arr[high], you bring an unknown value to mid. You must re-examine mid
before advancing. But after swapping with low, the value coming from low is always 1 (already
processed), so mid++ is safe.
Dry Run → [2, 0, 2, 1, 1, 0]
low=0,mid=0,high=5: arr[0]=2 → swap(0,5)=[0,0,2,1,1,2] high=4
low=0,mid=0,high=4: arr[0]=0 → swap(0,0) low=1 mid=1
low=1,mid=1,high=4: arr[1]=0 → swap(1,1) low=2 mid=2
low=2,mid=2,high=4: arr[2]=2 → swap(2,4)=[0,0,1,1,2,2] high=3
low=2,mid=2,high=3: arr[2]=1 → mid=3
low=2,mid=3,high=3: arr[3]=1 → mid=4 (mid>high, stop)
Result: [0, 0, 1, 1, 2, 2] ✔
Common Mistakes ✘
✘ Adding mid++ when swapping with high → skips the swapped-in element
✘ Using mid <= high (correct) vs mid < high (wrong — misses last element)
✘ Thinking this needs sorting — it's a single-pass partition, not a sort
ONE-LINE RECALL 3 pointers · low=0s · high=2s · mid scans · no mid++ when swap
with high
Time Complexity Space Complexity
O(n) — one single pass O(1) — in-place, no extra array
05 Container With Most Water [Medium]
Companies: Amazon · Apple · DE Shaw
What the problem wants
Given an array where each value is a wall height, find two walls that together hold the maximum amount of water.
Water amount = distance × min(height[left], height[right]).
Big Idea → Always move the SHORTER wall inward
The water is always limited by the shorter wall. Moving the taller wall can only make things worse
(same or smaller height, smaller width). So you move the shorter wall hoping for a taller one.
Pointer Setup
left → Starts at 0 (leftmost wall)
right ← Starts at n-1 (rightmost wall)
Formula
area = (right - left) × min(height[left], height[right])
maxArea = max(maxArea, area)
Decision Table (while left < right)
Condition Action
height[left] < left++ (left is shorter, move it)
height[right]
height[left] >= right-- (right is shorter or equal, move it)
height[right]
always maxArea = max(maxArea, area)
Dry Run → [1, 8, 6, 2, 5, 4, 8, 3, 7]
l=0,r=8: min(1,7)×8=8 maxArea=8. left++ (1<7)
l=1,r=8: min(8,7)×7=49 maxArea=49. right-- (8>=7)
l=1,r=7: min(8,3)×6=18 maxArea=49. right-- (8>=3)
l=1,r=6: min(8,8)×5=40 maxArea=49. right-- (8>=8)
...continue squeezing...
Result: 49 ✔
Why moving the taller wall never helps — intuition
Current area = width × min(left, right). If you move the taller wall, min(left,right) stays same or gets
worse, and width shrinks. Area can only get smaller. But if you move the shorter wall, min might
improve.
Common Mistakes ✘
✘ Moving the TALLER wall — never helps, always move shorter
✘ Forgetting width is (right - left), not just right
✘ Using left <= right — when they meet, width = 0, area = 0
ONE-LINE RECALL squeeze · compute area · move the SHORTER wall · track max
Time Complexity Space Complexity
O(n) — one pass O(1) — only two pointers + one
variable
06 Trapping Rain Water [Hard]
Companies: Amazon · Google · Facebook · Microsoft
What the problem wants
Given wall heights, compute how much rainwater gets trapped between the walls after it rains. Water at any
position = min(maxLeft, maxRight) - height[current].
Big Idea → Water at any spot is limited by the SHORTER surrounding wall
At every index, trapped water = min(tallest wall to its left, tallest wall to its right) − own height. Two
Pointer lets us compute this without storing left/right max arrays.
Pointer Setup
left → Starts at 0
right ← Starts at n-1
leftMax → Max height seen so far from the left
rightMa
x ← Max height seen so far from the right
Core Insight — Why Does This Work?
If leftMax < rightMax:
The bottleneck at position left is leftMax (we know rightMax is taller on the right side).
Water trapped at left = leftMax - height[left] (process left, then left++)
If rightMax <= leftMax:
The bottleneck at position right is rightMax.
Water trapped at right = rightMax - height[right] (process right, then right--)
Algorithm — Step by Step
left=0, right=n-1, leftMax=0, rightMax=0, water=0
while left < right:
if height[left] < height[right]:
if height[left] >= leftMax: leftMax = height[left]
else: water += leftMax - height[left]
left++
else:
if height[right] >= rightMax: rightMax = height[right]
else: water += rightMax - height[right]
right--
Dry Run → [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
l=0,r=11: h[0]=0<h[11]=1 → leftMax=0, water+=0-0=0, l++
l=1,r=11: h[1]=1=h[11]=1 → rightMax=1, r--
l=1,r=10: h[1]=1=h[10]=2 → leftMax=1, l++
l=2,r=10: h[2]=0<h[10]=2 → water+=1-0=1, l++
l=3,r=10: h[3]=2=h[10]=2 → leftMax=2, l++
...continuing...
Final water = 6 ✔
Common Mistakes ✘
✘ Updating leftMax/rightMax AFTER computing water → wrong values, use current height to update max first
✘ Thinking you need extra O(n) arrays → two pointer eliminates that need
✘ Processing both pointers in the same iteration → only process the side with the smaller max
✘ Using left <= right → pointers meeting means 0 width, skip that step
ONE-LINE RECALL leftMax vs rightMax · process the smaller side · water = max -
height · left++ or right--
Time Complexity Space Complexity
O(n) — one pass O(1) — four variables only
Master Summary
# Problem Sort Pointer Style One-Line Recall Time
ed?
0 Move Zeroes No → → same right scans · left places · swap non- O(n)
1 dir zero
0 Two Sum II Yes → ← too big→right-- · too small→left++ O(n)
2 squeeze
0 3Sum Yes fix i + → TwoSum inside for loop · skip dupes O(n²)
3 ←
0 Sort Colors No 3 ptr: 0→left · 1→mid · 2→right zones O(n)
4 low/mid/hi
gh
0 Container Most No → ← move the SHORTER wall · track max O(n)
5 Water squeeze area
0 Trapping Rain No → ← + 2 process smaller-max side · O(n)
6 Water maxes water=max-h
Pattern Recognition Cheat Sheet
USE SAME DIRECTION (→ →) when: USE OPPOSITE ENDS (→ ←) when:
• Moving/partitioning elements (zeros, odds, etc.) • Finding pairs/triplets summing to target
• No sorting needed • Maximising area or trapped quantity
• One pointer places, one pointer scans • Array is sorted (or can be sorted)
Example: Move Zeros, Sort Colors Example: Two Sum, 3Sum, Container, Rain Water