Coding Drills Β· 02

Two Pointers

Eleven drills built on one idea: two indices that each move in only one direction can cover an array in O(n) time and O(1) extra space. Opposite ends for sorted pairs and symmetric scans, read/write for in-place compaction, merge from the back, and reversal tricks for rotations and permutations β€” each with a traced diagram, a compilable Java solution and the bugs to avoid.

11
Drills
6
Easy
4
Medium
1
Hard
01 Arrays & Hashing Β· 02 Two Pointers Β· 03 Strings & Sliding Window Β· 04 Binary Search & Intervals Β· 05 Linked Lists Β· 06 Binary Trees & BST Β· 07 Grids & Matrices Β· 08 Graphs Β· 09 Dynamic Programming Β· 10 Backtracking & Design
01
Chapter One Β· Core Idea

Two Indices, One Pass

A brute-force pair search tries every (i, j): O(nΒ²). The two-pointer technique keeps two indices and, at each step, moves exactly one of them based on a local comparison. Because neither pointer ever moves backwards, the total number of moves is bounded by the array length β€” the whole scan is O(n), and since the state is just two integers, extra space is O(1).

What makes it correct is always a monotonic argument: in a sorted array, moving the left pointer can only increase a sum; in Container With Most Water, the shorter wall can never be part of a better answer; in a compaction, everything left of write is final. When you can state that argument in one sentence, you have a two-pointer solution.

Three ways to place two pointers
1 Β· OPPOSITE ENDS 1 3 5 7 9 11 L β†’ ← R converge; each step discards one end for good 2 Β· SAME DIRECTION 1 3 0 0 5 write read read scans everything; write keeps the survivors 3 Β· TWO SEQUENCES 1 4 7 2 3 8 i j take the smaller head, advance that pointer In every shape each pointer only moves forward (or only backward) β†’ at most n moves in total β†’ O(n), O(1) space
Analogy: Two people reading a palindrome aloud, one from each end. They compare letters, step inward together, and stop when they meet. Nobody ever re-reads a letter β€” that is why the check costs n/2 comparisons, not nΒ².
Two pointers vs. hashing (previous page):
  • Hashing buys O(n) time with O(n) memory and works on unsorted data.
  • Two pointers buys O(n) time with O(1) memory but needs structure: sorted order, a symmetric question, or an in-place rewrite.
  • If the input is sorted (or you are allowed to sort it), try two pointers first β€” Two Sum II (Drill 18) versus Two Sum (Drill 01) is the classic comparison.
02
Chapter Two Β· Mental Model

Why Moving One Pointer Is Safe

The array is sorted ascending and L < R
β–Ά
nums[L] + nums[R] too small β†’ every pair using nums[L] with anything left of R is also too small β†’ L can be discarded forever
Each step permanently discards one index
β–Ά
At most n βˆ’ 1 steps before L meets R β†’ O(n) time with no revisits
A read pointer scans while a write pointer marks the next free slot
β–Ά
Everything in [0, write) is final output; the array is rewritten in place with O(1) space
Two sorted inputs and the output overlaps one of them (Merge Sorted Array)
β–Ά
Fill from the back: the largest remaining element is known, and the back slots are empty β€” nothing unread is overwritten
Rotation and permutation questions rearrange whole segments
β–Ά
reverse(l, r) is itself a two-pointer swap loop; compositions of reversals rotate or reorder segments in O(n), O(1)
The answer depends on the smaller of two boundaries (water, containers)
β–Ά
Move the side that is the bottleneck β€” the other side cannot improve the answer until the bottleneck changes

Ask these questions in order; the first "yes" picks the template.

Pair / symmetric check on sorted data? two sum sorted, palindrome, container yes Opposite ends L = 0, R = n βˆ’ 1, converge no Filter or compact in place? remove dups, move zeroes, remove value yes Read / write for read; nums[write++] = … no Two sorted inputs to combine? merge arrays / lists, intersection yes Merge from the back if in place no Reorder whole segments? rotate, next permutation, reverse words yes Reverse ranges reverse(l, r) building block
03
Chapter Three Β· Pattern Toolkit

Four Reusable Templates

Every drill on this page is one of these four loops with a different comparison plugged in. Memorise the loop shapes and the invariants written in the comments β€” those invariants are what you say out loud in an interview.

Template A β€” Opposite Ends
Start at both ends and converge. Use when a pair/symmetric question has a monotonic rule telling you which end is useless.
Pseudocode
function converge(a): L = 0, R = n - 1 while L < R: if done(a[L], a[R]): return answer if leftIsUseless(a[L], a[R]): L = L + 1 else: R = R - 1 return notFound
Template A β€” opposite ends: is "racecar" a palindrome?
L=0 R=6 r a c e c a r L R 'r' == 'r' β†’ L++, R-- L=1 R=5 r a c e c a r L R 'a' == 'a' β†’ L++, R-- L=2 R=4 r a c e c a r L R 'c' == 'c' β†’ L++, R-- L=R=3 r a c e c a r L=R pointers met β†’ palindrome βœ“
Template B β€” Read / Write (Same Direction)
One pointer reads every element; the other marks where the next kept element goes. Invariant: a[0..write) is the finished output.
Pseudocode
function compact(a): write = 0 for read in 0 .. n-1: if keep(a[read]): a[write] = a[read] write = write + 1 return write // new logical length
Template B β€” read/write: remove every 3 from [3, 2, 2, 3, 4]
read=0 3 2 2 3 4 r,w nums[0]=3 == 3 β†’ skip read=1 2 2 2 3 4 r,w nums[1]=2 β‰  3 β†’ nums[0] = it, write++ read=2 2 2 2 3 4 r,w nums[2]=2 β‰  3 β†’ nums[1] = it, write++ read=3 2 2 2 3 4 r w nums[3]=3 == 3 β†’ skip read=4 2 2 4 3 4 r w nums[4]=4 β‰  3 β†’ nums[2] = it, write++ result: first write = 3 slots are [2, 2, 4]; the tail is "don't care"
Template C β€” Merge Two Sorted Sequences
One pointer per input; repeatedly take the smaller head. When writing into one of the inputs, run the same loop from the back so you never overwrite unread data.
Pseudocode
function merge(A, B): i = 0, j = 0 while i < len(A) or j < len(B): if j == len(B) or (i < len(A) and A[i] <= B[j]): out.add(A[i]); i = i + 1 else: out.add(B[j]); j = j + 1
Template C β€” merge [1, 4, 7] and [2, 3, 8] (green = from A, gold = from B)
A 1 4 7 B 2 3 8 out 1 2 3 4 7 8 1 2 3 4 5 6 order taken: 1 Β· 2 Β· 3 Β· 4 Β· 7 Β· 8 compare heads A[i] vs B[j], copy the smaller, advance that pointer; when one runs out, copy the other's tail
Template D β€” Reverse a Range
The opposite-ends loop with a swap. On its own it reverses strings; composed two or three times it rotates arrays and builds the next permutation.
Pseudocode
function reverse(a, lo, hi): while lo < hi: swap(a[lo], a[hi]) lo = lo + 1 hi = hi - 1
Template D β€” reverse a sub-range in place
start 9 1 2 3 4 8 lo hi reverse(a, 1, 4) swap 1 9 4 2 3 1 8 lo hi swap a[1], a[4] swap 2 9 4 3 2 1 8 swap a[2], a[3] β†’ lo β‰₯ hi, done
04
Drill 13 Β· Opposite Ends

Reverse String

Drill 13 Β· Reverse String

Reverse a character array s in place using O(1) extra memory.

Example
Input: s = ['h', 'e', 'l', 'l', 'o'] Output: ['o', 'l', 'l', 'e', 'h']
πŸ’‘ Key insight: Position i and position nβˆ’1βˆ’i simply trade places. Two pointers walking inward visit each of those mirror pairs exactly once, so n/2 swaps reverse the array.

Brute force β†’ optimal. Building a reversed copy (or new StringBuilder(str).reverse()) is O(n) time but O(n) space, which the problem forbids. Template D swaps in place: O(n) time, O(1) space. The middle element of an odd-length array never moves β€” the loop condition left < right skips it automatically.

Trace β€” reverse ["h","e","l","l","o"] in place
L=0 R=4 h e l l o L R swap 'h' ↔ 'o' L=1 R=3 o e l l h L R swap 'e' ↔ 'l' L=R=2 o l l e h L=R L β‰₯ R β†’ stop. Result "olleh"
Java β€” swap inward
import java.util.Arrays; public class ReverseString { public static void reverseString(char[] s) { int left = 0, right = s.length - 1; while (left < right) { char tmp = s[left]; s[left++] = s[right]; s[right--] = tmp; } } public static void main(String[] args) { char[] s = {'h', 'e', 'l', 'l', 'o'}; reverseString(s); System.out.println(Arrays.toString(s)); // [o, l, l, e, h] } }
Complexity
ApproachTimeSpaceNotes
Copy into a new arrayO(n)O(n)violates the in-place requirement
Two-pointer swap ← optimalO(n)O(1)n/2 swaps
⚠ Common bugs & edge cases:
  • Loop condition left <= right is harmless here (it swaps the middle with itself) but i < n instead of i < n / 2 in an index-based loop reverses twice β€” giving back the original.
  • Missing import java.util.Arrays for Arrays.toString in main β€” the original drill did not compile.
  • Java String is immutable; for a String input convert with toCharArray() and back with new String(chars).
05
Drill 14 Β· Read / Write

Move Zeroes

Drill 14 Β· Move Zeroes

Move all zeros in nums to the end while keeping the relative order of the non-zero elements. Modify the array in place.

Example
Input: nums = [0, 1, 0, 3, 12] Output: [1, 3, 12, 0, 0]
πŸ’‘ Key insight: This is Template B with "keep = non-zero" β€” but instead of copying and then zero-filling the tail, swap the kept element with the slot at write. The zeros get pushed rightwards as a side effect, in a single pass.

Brute force β†’ optimal. Bubbling each zero to the end is O(nΒ²). Copying non-zeros into a new array is O(n) but uses O(n) space. The read/write swap is O(n), O(1) and stable for the non-zero values. (Copy-then-fill is equally valid; swapping does fewer writes when there are few zeros.)

Trace β€” move zeroes in [0, 1, 0, 3, 12] (state after each step)
read=0 0 1 0 3 12 read=write zero β†’ skip read=1 1 0 0 3 12 read=write 1 β‰  0 β†’ swap a[0], a[1], write++ read=2 1 0 0 3 12 read write zero β†’ skip read=3 1 3 0 0 12 read write 3 β‰  0 β†’ swap a[1], a[3], write++ read=4 1 3 12 0 0 read write 12 β‰  0 β†’ swap a[2], a[4], write++ green = finished prefix of non-zeros Β· dashed = zeros drifting right
Java β€” read/write with swap
import java.util.Arrays; public class MoveZeroes { public static void moveZeroes(int[] nums) { int write = 0; // next slot for a non-zero for (int read = 0; read < nums.length; read++) { if (nums[read] != 0) { int tmp = nums[write]; // swap keeps zeroes flowing right nums[write] = nums[read]; nums[read] = tmp; write++; } } } public static void main(String[] args) { int[] nums = {0, 1, 0, 3, 12}; moveZeroes(nums); System.out.println(Arrays.toString(nums)); // [1, 3, 12, 0, 0] } }
Complexity
ApproachTimeSpaceNotes
Bubble zeros one by oneO(nΒ²)O(1)
Copy to new arrayO(n)O(n)
Read/write swap ← optimalO(n)O(1)single pass, stable
⚠ Common bugs & edge cases:
  • Sorting β€” it reorders the non-zero values, breaking the "relative order" requirement.
  • Using opposite-ends swapping (zero at left, non-zero at right) β€” fast, but also destroys the order.
  • Copy-then-fill variant: forgetting the second loop that writes zeros into [write, n) leaves stale values.
06
Drill 15 Β· Read / Write

Remove Duplicates from Sorted Array

Drill 15 Β· Remove Duplicates from Sorted Array
Easy read / write LeetCode #26 β†—

Given a sorted array, remove duplicates in place so each value appears once, keep the order, and return k β€” the number of unique values. The first k slots must hold the result.

Example
Input: nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] Output: 5, nums = [0, 1, 2, 3, 4, _, _, _, _, _]
πŸ’‘ Key insight: Sorted means duplicates are adjacent. "Keep" is simply "different from the last value I kept" β€” compare with nums[k βˆ’ 1], the tail of the output.

Brute force β†’ optimal. A LinkedHashSet rebuild is O(n) time but O(n) space; shifting elements left on every duplicate is O(nΒ²). Template B with "keep if nums[i] != nums[k βˆ’ 1]" is O(n), O(1). Comparing against the last kept value (rather than nums[i βˆ’ 1]) generalises directly to LC 80 "allow at most two" by comparing with nums[k βˆ’ 2].

inums[i]last kept nums[kβˆ’1]actionk after
100dup β€” skip1
210nums[1] = 12
3, 41, 11dup β€” skip2
521nums[2] = 23
622dup β€” skip3
732nums[3] = 34
833dup β€” skip4
943nums[4] = 45
Remove duplicates from [0,0,1,1,1,2,2,3,3,4]
before 0 0 1 1 1 2 2 3 3 4 dup new dup dup new dup new dup new after 0 1 2 3 4 2 2 3 3 4 k = 5 only nums[0..k) is meaningful; the tail keeps whatever was there (LeetCode ignores it)
Java β€” compare with the last kept value
import java.util.Arrays; public class RemoveDuplicates { public static int removeDuplicates(int[] nums) { if (nums.length == 0) return 0; int k = 1; // nums[0..k-1] holds the unique values for (int i = 1; i < nums.length; i++) { if (nums[i] != nums[k - 1]) nums[k++] = nums[i]; } return k; } public static void main(String[] args) { int[] nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4}; int k = removeDuplicates(nums); System.out.println(k + " " + Arrays.toString(Arrays.copyOf(nums, k))); // 5 [0, 1, 2, 3, 4] } }
Complexity
ApproachTimeSpaceNotes
Shift left on each duplicateO(nΒ²)O(1)
LinkedHashSet rebuildO(n)O(n)
Read/write ← optimalO(n)O(1)
⚠ Common bugs & edge cases:
  • Forgetting the nums.length == 0 guard β€” k = 1 would claim one element in an empty array.
  • Returning the array instead of k, or printing the whole array (the tail is garbage by design).
  • Applying this to an unsorted array β€” duplicates are no longer adjacent; you need a hash set.
07
Drill 16 Β· Merge

Merge Two Sorted Arrays

Drill 16 Β· Merge Two Sorted Arrays
Easy merge from back LeetCode #88 β†—

nums1 has length m + n: its first m values are sorted and the last n slots are empty. Merge the sorted array nums2 (length n) into nums1 so the whole thing is sorted, in place.

Example
Input: nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3 Output: nums1 = [1, 2, 2, 3, 5, 6]
πŸ’‘ Key insight: Merging from the front would overwrite nums1 values you have not read yet. The back of nums1 is empty, and the largest remaining element is always one of the two tails β€” so fill from the back.

Brute force β†’ optimal. Copy nums2 into the tail and call Arrays.sort: O((m+n) log(m+n)). A forward merge into a temporary array is O(m+n) time but O(m) space. The backward merge is O(m+n) time and O(1) space. Loop on j >= 0 only: once nums2 is exhausted, whatever remains of nums1 is already sorted and in place.

Trace β€” merge from the back: nums1 = [1, 2, 3, _, _, _], nums2 = [2, 5, 6]
start 1 2 3 0 0 0 i w nums2 = [2, 5, 6], j = 2 step 1 1 2 3 0 0 6 i w 3 ≀ 6 β†’ take nums2[2] = 6 step 2 1 2 3 0 5 6 i w 3 ≀ 5 β†’ take nums2[1] = 5 step 3 1 2 3 3 5 6 i w 3 > 2 β†’ take nums1[2] step 4 1 2 2 3 5 6 2 ≀ 2 β†’ take nums2[0] = 2 j < 0 β†’ stop; nums1[0..i] already in place
Java β€” three pointers from the back
import java.util.Arrays; public class MergeSortedArray { // nums1 has length m + n; its last n slots are empty buffer. public static void merge(int[] nums1, int m, int[] nums2, int n) { int i = m - 1, j = n - 1, write = m + n - 1; while (j >= 0) { // once nums2 is used up, nums1's rest is already in place if (i >= 0 && nums1[i] > nums2[j]) nums1[write--] = nums1[i--]; else nums1[write--] = nums2[j--]; } } public static void main(String[] args) { int[] nums1 = {1, 2, 3, 0, 0, 0}; merge(nums1, 3, new int[]{2, 5, 6}, 3); System.out.println(Arrays.toString(nums1)); // [1, 2, 2, 3, 5, 6] } }
Complexity
ApproachTimeSpaceNotes
Copy + sortO((m+n) log(m+n))O(log(m+n))sort stack
Forward merge with a copy of nums1O(m + n)O(m)
Backward merge ← optimalO(m + n)O(1)
⚠ Common bugs & edge cases:
  • Merging front-to-back in place β€” overwrites nums1[i] before it is read.
  • Looping on i >= 0 && j >= 0 and forgetting to drain the rest of nums2 (e.g. nums1 = [4,5,6,0,0,0], nums2 = [1,2,3]). The original drill handled it with a second loop; the single while (j >= 0) loop with an i >= 0 guard covers both.
  • m = 0: i starts at βˆ’1 and every element comes from nums2 β€” the guard i >= 0 prevents an out-of-bounds read.
08
Drill 17 Β· Reverse Ranges

Rotate Array

Drill 17 Β· Rotate Array

Rotate nums to the right by k steps, in place. k may be larger than the array length.

Example
Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3 Output: [5, 6, 7, 1, 2, 3, 4]
πŸ’‘ Key insight: A right rotation by k swaps two blocks: [A | B] β†’ [B | A] where B is the last k elements. Reversing the whole array gives [BΚ³ | AΚ³]; reversing each block again restores their internal order.

Brute force β†’ optimal. Rotating by one, k times, is O(nΒ·k). Copying into result[(i + k) % n] is O(n) time but O(n) space. Three reversals (Template D) are O(n) time β€” each element is swapped at most twice β€” and O(1) space. Always reduce k %= n first.

Trace β€” rotate [1..7] right by 3 with three reversals
start 1 2 3 4 5 6 7 k = 3 (k % 7 = 3) rev all 7 6 5 4 3 2 1 reverse(0, 6) rev [0,k) 5 6 7 4 3 2 1 reverse(0, 2) rev [k,n) 5 6 7 1 2 3 4 reverse(3, 6) β†’ done the last k elements must end up first: reversing everything moves them to the front (backwards), two more reversals fix the order
Java β€” three reversals
import java.util.Arrays; public class RotateArray { public static void rotate(int[] nums, int k) { int n = nums.length; if (n == 0) return; // avoid k % 0 k %= n; reverse(nums, 0, n - 1); // whole array reverse(nums, 0, k - 1); // first k reverse(nums, k, n - 1); // remaining n - k } private static void reverse(int[] nums, int lo, int hi) { while (lo < hi) { int tmp = nums[lo]; nums[lo++] = nums[hi]; nums[hi--] = tmp; } } public static void main(String[] args) { int[] nums = {1, 2, 3, 4, 5, 6, 7}; rotate(nums, 3); System.out.println(Arrays.toString(nums)); // [5, 6, 7, 1, 2, 3, 4] } }
Complexity
ApproachTimeSpaceNotes
Rotate by one, k timesO(nΒ·k)O(1)
Extra array, index (i + k) % nO(n)O(n)
Three reversals ← optimalO(n)O(1)
⚠ Common bugs & edge cases:
  • Forgetting k %= n: with k = 10, n = 7, reverse(0, k βˆ’ 1) indexes past the end.
  • Empty array: k % 0 throws ArithmeticException β€” the original drill had no guard; return early when n == 0.
  • Reversing the blocks in the wrong order for a left rotation: left by k = right by n βˆ’ k.
09
Drill 18 Β· Opposite Ends

Two Sum II (Sorted Input)

Drill 18 Β· Two Sum II β€” Input Array Is Sorted

Given a 1-indexed array numbers sorted in non-decreasing order, find two numbers that add up to target and return their indices [index1, index2] (1-based, index1 < index2). Use only O(1) extra space.

Example
Input: numbers = [2, 7, 11, 15], target = 9 Output: [1, 2] Input: numbers = [1, 3, 4, 6, 8, 11], target = 10 Output: [3, 4] // 4 + 6
πŸ’‘ Key insight: If numbers[L] + numbers[R] is too small, then numbers[L] plus anything at or left of R is too small too (R is the biggest still available) β€” so L is useless and can go. Symmetrically, too big means R is useless.

Brute force β†’ optimal. All pairs: O(nΒ²). For each element, binary-search its complement: O(n log n), O(1). The Drill 01 hash map is O(n) but O(n) space, which this problem forbids. Opposite-ends convergence is O(n) and O(1) and uses the sortedness that the hash map ignores.

Trace β€” numbers = [1, 3, 4, 6, 8, 11], target = 10
L=0 R=5 1 3 4 6 8 11 L R 1 + 11 = 12 > 10 β†’ R-- L=0 R=4 1 3 4 6 8 11 L R 1 + 8 = 9 < 10 β†’ L++ L=1 R=4 1 3 4 6 8 11 L R 3 + 8 = 11 > 10 β†’ R-- L=1 R=3 1 3 4 6 8 11 L R 3 + 6 = 9 < 10 β†’ L++ L=2 R=3 1 3 4 6 8 11 L R 4 + 6 = 10 == 10 β†’ return [3, 4] dashed = discarded for good: no partner for it can exist inside the remaining window
Java β€” converge from both ends
import java.util.Arrays; public class TwoSumII { // numbers is sorted ascending; answer is 1-indexed. public static int[] twoSum(int[] numbers, int target) { int left = 0, right = numbers.length - 1; while (left < right) { int sum = numbers[left] + numbers[right]; if (sum == target) return new int[]{left + 1, right + 1}; if (sum < target) left++; // need a bigger sum else right--; // need a smaller sum } return new int[]{-1, -1}; } public static void main(String[] args) { System.out.println(Arrays.toString(twoSum(new int[]{2, 7, 11, 15}, 9))); // [1, 2] System.out.println(Arrays.toString(twoSum(new int[]{1, 3, 4, 6, 8, 11}, 10))); // [3, 4] } }
Complexity
ApproachTimeSpaceNotes
All pairsO(nΒ²)O(1)
Binary search per elementO(n log n)O(1)
Hash map (Drill 01)O(n)O(n)ignores sortedness
Opposite ends ← optimalO(n)O(1)
⚠ Common bugs & edge cases:
  • Returning 0-based indices β€” this problem is 1-indexed.
  • while (left <= right) lets an element pair with itself (e.g. target 8 with a single 4).
  • Overflow when values are near Integer.MAX_VALUE: compute the sum as long or compare numbers[L] < target βˆ’ numbers[R].
10
Drill 19 Β· Opposite Ends

Reverse Vowels of a String

Drill 19 Β· Reverse Vowels of a String
Easy opposite ends + skip LeetCode #345 β†—

Reverse only the vowels (a e i o u, upper or lower case) of a string; every other character stays where it is.

Example
Input: s = "hello" Output: "holle" Input: s = "leetcode" Output: "leotcede"
πŸ’‘ Key insight: It is Reverse String on a filtered view: the vowels form a hidden sub-array, and the two pointers simply hop over consonants until both land on a vowel, then swap.

Brute force β†’ optimal. Collect vowels into a list, then write them back in reverse: O(n) time, O(n) space, two passes. Two pointers that skip non-vowels do it in one pass with O(1) extra space (beyond the char array a Java String forces you to make). Each pointer moves monotonically, so total work is O(n) even with the inner skip loops.

StepL (char)R (char)Actionchars after
10 l β†’ 1 e7 eL skips l; swap e ↔ eleetcode
22 e6 d β†’ 5 oR skips d; swap e ↔ oleotcede
33 t β†’ 4 c4L reaches R (L < R fails) β€” no vowel leftleotcede
Java β€” inward scan, skip consonants
public class ReverseVowels { private static boolean isVowel(char c) { return "aeiouAEIOU".indexOf(c) >= 0; } public static String reverseVowels(String s) { char[] chars = s.toCharArray(); int left = 0, right = chars.length - 1; while (left < right) { while (left < right && !isVowel(chars[left])) left++; while (left < right && !isVowel(chars[right])) right--; char tmp = chars[left]; chars[left++] = chars[right]; chars[right--] = tmp; } return new String(chars); } public static void main(String[] args) { System.out.println(reverseVowels("hello")); // holle System.out.println(reverseVowels("leetcode")); // leotcede } }
Complexity
ApproachTimeSpaceNotes
Collect vowels, write back reversedO(n)O(n)two passes
Two pointers with skip loops ← optimalO(n)O(1) extraplus the unavoidable char[] copy
⚠ Common bugs & edge cases:
  • Inner skip loops without left < right run off the end on strings with no vowels (e.g. "xyz").
  • Forgetting uppercase vowels β€” "aA" must become "Aa".
  • Not advancing both pointers after a swap: the loop swaps the same pair forever.
11
Drill 20 Β· Bottleneck Pointers

Container With Most Water

Drill 20 Β· Container With Most Water
Medium opposite ends Β· move shorter LeetCode #11 β†— Full write-up β†’

height[i] is a vertical line at x = i. Pick two lines that, with the x-axis, hold the most water; return that area min(height[L], height[R]) Γ— (R βˆ’ L).

Example
Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7] Output: 49 // lines 1 and 8: min(8, 7) Γ— 7
πŸ’‘ Key insight: Start with the widest container. Any narrower container that keeps the shorter wall can only be worse (less width, height still capped by that wall). So the shorter wall is useless from now on β€” move it inward and hope for a taller one.

Brute force β†’ optimal. Every pair is O(nΒ²). Opposite ends with "move the shorter wall" is O(n): each step discards one line with a proof that it cannot be in a better pair. On ties either side may move β€” both walls are the bottleneck.

height = [1, 8, 6, 2, 5, 4, 8, 3, 7] β€” the shaded water is the optimum
1 0 8 1 6 2 2 3 5 4 4 5 8 6 3 7 7 8 best pair L = 1, R = 8 min(8, 7) Γ— 7 = 49
L, Rareabestmove
0, 8min(1,7) Γ— 8 = 88L++ (h[L]=1 < h[R]=7)
1, 8min(8,7) Γ— 7 = 4949R-- (h[L]=8 β‰₯ h[R]=7)
1, 7min(8,3) Γ— 6 = 1849R-- (h[L]=8 β‰₯ h[R]=3)
1, 6min(8,8) Γ— 5 = 4049R-- (h[L]=8 β‰₯ h[R]=8)
1, 5min(8,4) Γ— 4 = 1649R-- (h[L]=8 β‰₯ h[R]=4)
1, 4min(8,5) Γ— 3 = 1549R-- (h[L]=8 β‰₯ h[R]=5)
1, 3min(8,2) Γ— 2 = 449R-- (h[L]=8 β‰₯ h[R]=2)
1, 2min(8,6) Γ— 1 = 649R-- (h[L]=8 β‰₯ h[R]=6)
Java β€” move the shorter wall
public class ContainerMostWater { public static int maxArea(int[] height) { int left = 0, right = height.length - 1, best = 0; while (left < right) { int area = Math.min(height[left], height[right]) * (right - left); best = Math.max(best, area); if (height[left] < height[right]) left++; // the shorter wall is the bottleneck else right--; } return best; } public static void main(String[] args) { System.out.println(maxArea(new int[]{1, 8, 6, 2, 5, 4, 8, 3, 7})); // 49 } }
Complexity
ApproachTimeSpaceNotes
All pairsO(nΒ²)O(1)
Opposite ends ← optimalO(n)O(1)n βˆ’ 1 steps
⚠ Common bugs & edge cases:
  • Moving the taller wall: the area can only shrink, so the optimum (1, 8) above would be skipped.
  • Using the sum of heights or the area under the bars β€” the container is a rectangle limited by the shorter wall.
  • Confusing this with Trapping Rain Water (next drill), which sums water over every index.
12
Drill 21 Β· Bottleneck Pointers

Trapping Rain Water

Drill 21 Β· Trapping Rain Water
Hard opposite ends Β· running max LeetCode #42 β†— Full write-up β†’

Given non-negative bar heights of width 1, compute how many units of rain water are trapped after raining.

Example
Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] Output: 6 Input: height = [4, 2, 0, 3, 2, 5] Output: 9
πŸ’‘ Key insight: Water above bar i rises to the lower of the two tallest walls around it: min(maxLeft[i], maxRight[i]) βˆ’ h[i]. You do not need both maxima exactly β€” only to know which side is lower. If the running leftMax is below the running rightMax, the true right maximum can only be higher still, so the left side decides index L right now.

Brute force β†’ optimal. For each index scan left and right for the maxima: O(nΒ²). Precomputing maxLeft[] and maxRight[] arrays: O(n) time, O(n) space. A monotonic stack also gives O(n)/O(n). Two pointers with two running maxima settle one index per step: O(n) time, O(1) space.

Elevation [0,1,0,2,1,0,1,3,2,1,2,1] β€” blue is trapped water
0 0 1 1 +1 0 2 2 3 +1 1 4 +2 0 5 +1 1 6 3 7 2 8 +1 1 9 2 10 1 11 h i water[i] = min(max height on the left, max height on the right) βˆ’ h[i] β†’ 1 + 1 + 2 + 1 + 1 = 6
sideleftMax, rightMaxdecisiontotal
L=00, 1leftMax < rightMax β†’ water[0] = 0 βˆ’ 0 = 00
R=111, 1leftMax β‰₯ rightMax β†’ water[11] = 1 βˆ’ 1 = 00
L=11, 2leftMax < rightMax β†’ water[1] = 1 βˆ’ 1 = 00
L=21, 2leftMax < rightMax β†’ water[2] = 1 βˆ’ 0 = 11
R=102, 2leftMax β‰₯ rightMax β†’ water[10] = 2 βˆ’ 2 = 01
R=92, 2leftMax β‰₯ rightMax β†’ water[9] = 2 βˆ’ 1 = 12
R=82, 2leftMax β‰₯ rightMax β†’ water[8] = 2 βˆ’ 2 = 02
L=32, 3leftMax < rightMax β†’ water[3] = 2 βˆ’ 2 = 02
L=42, 3leftMax < rightMax β†’ water[4] = 2 βˆ’ 1 = 13
L=52, 3leftMax < rightMax β†’ water[5] = 2 βˆ’ 0 = 25
L=62, 3leftMax < rightMax β†’ water[6] = 2 βˆ’ 1 = 16
Java β€” two pointers, two running maxima
public class TrappingRainWater { public static int trap(int[] height) { int left = 0, right = height.length - 1; int leftMax = 0, rightMax = 0, water = 0; while (left < right) { leftMax = Math.max(leftMax, height[left]); rightMax = Math.max(rightMax, height[right]); if (leftMax < rightMax) { water += leftMax - height[left++]; // left side is the bottleneck } else { water += rightMax - height[right--]; // right side is the bottleneck } } return water; } public static void main(String[] args) { System.out.println(trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1})); // 6 System.out.println(trap(new int[]{4, 2, 0, 3, 2, 5})); // 9 } }
Complexity
ApproachTimeSpaceNotes
Scan both sides per indexO(nΒ²)O(1)
Prefix max + suffix max arraysO(n)O(n)easiest correct version
Monotonic stackO(n)O(n)fills water layer by layer
Two pointers ← optimalO(n)O(1)
⚠ Common bugs & edge cases:
  • Updating the max after computing water β€” leftMax βˆ’ h[L] can go negative. Update first, then add (the difference is then β‰₯ 0).
  • Comparing height[L] < height[R] instead of the running maxima is a valid variant only if you are consistent; mixing the two conditions double-counts or misses water.
  • Fewer than 3 bars can trap nothing; the loop handles it, but test [], [5], [2, 0].
13
Drill 22 Β· Reverse Ranges

Next Permutation

Drill 22 Β· Next Permutation
Medium scan from right + reverse LeetCode #31 β†—

Rearrange nums into the lexicographically next greater permutation, in place with O(1) extra memory. If it is already the largest (fully descending), rearrange it into the smallest (ascending).

Example
Input: nums = [1, 2, 3] Output: [1, 3, 2] Input: nums = [1, 3, 5, 4, 2] Output: [1, 4, 2, 3, 5] Input: nums = [3, 2, 1] Output: [1, 2, 3]
πŸ’‘ Key insight: Think of an odometer. The longest descending suffix is "maxed out" β€” no rearrangement of it is bigger. So bump the digit just before it (the pivot) by the smallest possible amount β€” swap with the next-larger digit from the suffix β€” and reset the suffix to its smallest arrangement (ascending), which is just a reversal because it is still descending.

Brute force β†’ optimal. Generating all permutations and sorting them is O(n!Β·n). The three-step algorithm β€” find pivot, swap with its successor, reverse the suffix β€” is O(n) time and O(1) space. Both scans move one pointer leftwards; the reversal is Template D.

Trace β€” next permutation of [1, 3, 5, 4, 2]
1 pivot 1 3 5 4 2 i from the right, first a[i] < a[i+1]: 3 < 5 β†’ pivot i = 1; suffix [5,4,2] is descending 2 find j 1 3 5 4 2 i j rightmost a[j] > 3: 2 no, 4 yes β†’ j = 3 3 swap 1 4 5 3 2 swap β†’ [1,4,5,3,2]; suffix still descending 4 reverse 1 4 2 3 5 reverse suffix (2..4) β†’ [1,4,2,3,5]
Java β€” pivot, swap, reverse
import java.util.Arrays; public class NextPermutation { public static void nextPermutation(int[] nums) { int i = nums.length - 2; while (i >= 0 && nums[i] >= nums[i + 1]) i--; // 1. find the pivot if (i >= 0) { int j = nums.length - 1; while (nums[j] <= nums[i]) j--; // 2. rightmost element > pivot swap(nums, i, j); } reverse(nums, i + 1, nums.length - 1); // 3. suffix -> ascending } private static void swap(int[] a, int i, int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } private static void reverse(int[] a, int lo, int hi) { while (lo < hi) swap(a, lo++, hi--); } public static void main(String[] args) { int[] a = {1, 3, 5, 4, 2}; nextPermutation(a); System.out.println(Arrays.toString(a)); // [1, 4, 2, 3, 5] int[] b = {3, 2, 1}; nextPermutation(b); System.out.println(Arrays.toString(b)); // [1, 2, 3] } }
Complexity
ApproachTimeSpaceNotes
Enumerate all permutationsO(n!Β·n)O(n!)
Pivot + swap + reverse ← optimalO(n)O(1)at most 3 linear scans
⚠ Common bugs & edge cases:
  • Using > instead of >= in the pivot scan: with duplicates ([1, 5, 1]) you pick a wrong pivot. The suffix must be non-increasing.
  • Sorting the suffix instead of reversing it β€” correct but O(n log n); after the swap the suffix is still non-increasing, so a reversal suffices.
  • Forgetting the "no pivot" case (i == -1): skip the swap and reverse the whole array.
  • Picking the first element larger than the pivot from the left of the suffix instead of the rightmost one β€” gives a permutation that is too large.
14
Drill 23 Β· Prefix vs. Total

Partition Array into Two Equal Sum Subarrays

Drill 23 Β· Partition Array into Two Equal Sum Subarrays
Easy prefix vs. total Classic drill β€” no direct LeetCode twin

Given an integer array (values may be negative), decide whether it can be cut at one position into a non-empty left part and a non-empty right part β€” both contiguous β€” whose sums are equal. Return the cut index (last index of the left part) or βˆ’1.

Example
Input: nums = [1, 2, 3, 4, 5, 5] Output: 3 // [1,2,3,4] = 10 = [5,5] Input: nums = [1, 5, 11, 5] Output: -1 // prefix sums 1, 6, 17 never equal 11 Input: nums = [2, -1, 3, 2, 2] Output: 2 // [2,-1,3] = 4 = [2,2]
πŸ’‘ Key insight: The left and right parts are a pair of pointers on the sum: everything left of the cut, and everything right of it. As the cut moves one step right, one element crosses from right to left. Keep left as a running sum and get right for free as total βˆ’ left.

Brute force β†’ optimal. For each cut, sum both sides: O(nΒ²). One pass to get the total and one pass with a running left sum: O(n) time, O(1) space. Checking 2 Β· left == total avoids the "is total even?" special case and integer-division bugs. Note this is not LC 416 "Partition Equal Subset Sum" (any subset, not contiguous) β€” that one is a knapsack DP, covered on the dynamic programming page.

Running left sum vs. total on [1, 2, 3, 4, 5, 5]
nums 1 2 3 4 5 5 left sum 1 2Β·1=2 3 2Β·3=6 6 2Β·6=12 10 2Β·10=20 15 2Β·15=30 β€” right must be non-empty total = 20 stop when 2Β·left == total cut after index 3: [1,2,3,4] = 10 | [5,5] = 10
Java β€” total, then running left sum
public class PartitionEqualSum { // Can nums be cut at one index into a non-empty LEFT and RIGHT part with equal sums? // Returns the cut index (left = [0..i], right = [i+1..n-1]) or -1. public static int splitIndex(int[] nums) { long total = 0; for (int num : nums) total += num; long left = 0; for (int i = 0; i < nums.length - 1; i++) { // right part must be non-empty left += nums[i]; if (left * 2 == total) return i; // left == total - left } return -1; } public static boolean canSplit(int[] nums) { return splitIndex(nums) >= 0; } public static void main(String[] args) { System.out.println(splitIndex(new int[]{1, 2, 3, 4, 5, 5})); // 3 -> [1,2,3,4] | [5,5] System.out.println(canSplit(new int[]{1, 5, 11, 5})); // false (prefix sums 1, 6, 17) System.out.println(splitIndex(new int[]{2, -1, 3, 2, 2})); // 2 -> [2,-1,3] | [2,2] } }
Complexity
ApproachTimeSpaceNotes
Sum both sides for every cutO(nΒ²)O(1)
Total + running left sum ← optimalO(n)O(1)long avoids overflow
⚠ Common bugs & edge cases:
  • The original drill claimed [1, 5, 11, 5] returns true via [1, 11] + [5, 5] β€” those parts are not contiguous. With contiguous parts the answer is false (and the original code actually printed false).
  • Early exit if (sum > target) return false is wrong once negatives are allowed: [2, -1, 3, 2, 2] crosses half and comes back.
  • Letting the cut sit after the last element: [0] or [3, -3] would "split" into a part and an empty part. Loop to n βˆ’ 2.
  • int overflow on large inputs: accumulate in long.
15
Chapter Fifteen Β· Review

Summary & What to Practice Next

DrillProblemPatternTimeSpaceDifficulty
13Reverse Stringopposite endsO(n)O(1)Easy
14Move Zeroesread / writeO(n)O(1)Easy
15Remove Duplicates from Sorted Arrayread / writeO(n)O(1)Easy
16Merge Two Sorted Arraysmerge from backO(m + n)O(1)Easy
17Rotate Arrayreverse rangesO(n)O(1)Medium
18Two Sum II (sorted)opposite endsO(n)O(1)Medium
19Reverse Vowels of a Stringopposite ends + skipO(n)O(1)*Easy
20Container With Most Watermove shorter wallO(n)O(1)Medium
21Trapping Rain Waterrunning max pointersO(n)O(1)Hard
22Next Permutationpivot + reverseO(n)O(1)Medium
23Partition into Two Equal Sum Subarraysprefix vs. totalO(n)O(1)Easy

* O(1) beyond the char[] copy that Java's immutable String requires.

βˆ‘ Two Pointers β€” what to remember
  • Say the discard argument out loud β€” "L can never be part of a better answer because…". If you cannot, two pointers is probably the wrong tool (Drills 18, 20, 21).
  • Read/write invariant: a[0..write) is final. Only the keep-condition changes between problems (Drills 14, 15).
  • In-place merge? Go backwards β€” the empty space is at the back (Drill 16).
  • Reversal is a building block: rotate = three reversals; next permutation = pivot, swap, reverse (Drills 13, 17, 22).
  • Guard every inner loop with L < R and every % n with n > 0 (Drills 17, 19).
Practice next: