Arrays — Memory Model & Fundamentals
Contiguous block — O(1) random access via arithmetic:
address(i) = base + (i × element_size)
Index: [0] [1] [2] [3] [4]
Addr: 0x1000 0x1004 0x1008 0x100C 0x1010
Value: 10 20 30 40 50
└─ 4 bytes per Int ─┘
- Random access O(1): one addition + one memory load, regardless of array size
- Cache lines: CPU loads 64 bytes at once —
arr[0] prefetches arr[0..15] into L1 cache (~1ns vs ~100ns RAM)
- Sequential array traversal is 5-20x faster than linked list traversal due to cache locality
- Static arrays (
IntArray) are fixed size; dynamic arrays (MutableList) auto-resize at 2x capacity
- Dynamic array amortized append: O(1) — total copy work over n inserts = 1+2+4+...+n = 2n
Primitive arrays store raw values inline (no boxing). Reference arrays store heap-allocated object pointers. For 1M ints: IntArray = 4MB, Array<Int> = ~16MB.
| Type | JVM | Size | Use |
|---|
IntArray | int[] | 4B | Integer math — no boxing |
LongArray | long[] | 8B | Large integers |
DoubleArray | double[] | 8B | Floating point |
BooleanArray | boolean[] | 1B | Flags, visited arrays |
CharArray | char[] | 2B | Character manipulation |
Array<T> | T[] | 8B ref | Objects, nullables |
PREFER IntArray over Array<Int> — no boxing, cache-friendly, 4x less memory
// ── Creation ──
val zeros = IntArray(5) // [0,0,0,0,0]
val evens = IntArray(5) { it * 2 } // [0,2,4,6,8]
val primes = intArrayOf(2,3,5,7,11)
val words = Array(4) { "w$it" } // [w0,w1,w2,w3]
val grid = Array(3) { IntArray(4) } // 3x4 matrix
val nulls = arrayOfNulls<String>(3)
// ── Access — all O(1) ──
arr[0] arr.first() arr.last()
arr.getOrNull(10) // null if OOB
arr.getOrElse(10) { -1 } // fallback
// ── Mutation — O(1) ──
arr[0] = 99
arr.fill(0) arr.fill(7, 1, 4)
// ── Properties ──
arr.size arr.indices arr.lastIndex
// ── Destructuring ──
val (a, b, c) = arrayOf(1, 2, 3)
// ── Equality & Printing ──
arr1.contentEquals(arr2) // compare VALUES
arr.contentToString() // "[1, 2, 3]"
m.contentDeepToString() // 2D arrays
// ── Swap (extension) ──
fun IntArray.swap(i: Int, j: Int) {
val t = this[i]; this[i] = this[j]; this[j] = t
}
// Index loop
for (i in arr.indices) { arr[i] }
// Value loop
for (v in arr) { v }
// Index + value
for ((i,v) in arr.withIndex()) { }
arr.forEachIndexed { i, v -> }
// Reverse
for (i in arr.indices.reversed()) { }
// Step
for (i in arr.indices step 2) { }
// While (manual pointer)
var i = 0
while (i < arr.size) { i++ }
// ── Sorting — O(n log n) TimSort ──
arr.sort() // in-place
arr.sortedArray() // new copy
arr.sortDescending() // in-place desc
words.sortWith(compareBy { it.length })
students.sortWith(
compareByDescending<Student> { it.grade }
.thenBy { it.age })
// ── Searching ──
arr.indexOf(5) // O(n) linear
5 in arr // O(n) contains
arr.indexOfFirst { it > 3 }
sorted.binarySearch(6) // O(log n)
// ── Aggregates ──
arr.min() arr.max() arr.sum()
arr.average() arr.count { it > 0 }
// ── Copying ──
arr.copyOf() // full copy
arr.copyOf(3) // truncate
arr.copyOfRange(1, 4) // [1,4)
// ── Slicing → returns List ──
arr.slice(1..3)
arr.take(3) arr.drop(2)
arr.takeLast(2) arr.dropLast(1)
arr.takeWhile { it < 5 }
// ── Reverse ──
arr.reversed() // List copy
arr.reversedArray() // IntArray copy
// ── Concatenate ──
val combined = a + b // [1,2,3,4,5,6]
// ── Conversions ──
list.toIntArray() arr.toList()
arr.toMutableList() list.toTypedArray()
All return new collections — original is never mutated.
// Transform
arr.map { it * 2 }
arr.mapIndexed { i, v -> "$i=$v" }
arr.flatMap { listOf(it, it * 10) }
// Filter
arr.filter { it % 2 == 0 }
arr.filterNot { it < 0 }
arr.filterIndexed { i, _ -> i % 2 == 0 }
// Aggregate
arr.fold(0) { acc, v -> acc + v }
arr.reduce { acc, v -> acc * v }
arr.sumOf { it.toLong() }
// Predicate checks
arr.any { it > 9 }
arr.all { it > 0 }
arr.none { it < 0 }
// Split & Group
val (evens, odds) = arr.partition { it%2==0 }
arr.groupBy { if (it%2==0) "E" else "O" }
// Build & Combine
arr.associate { it to it * it } // Map
arr.zip(other) { a, b -> a + b }
arr.distinct() // no dupes
Internal buffer resizes at capacity:
[1 2 3 4 _ _ _ _] size=4, cap=8
↑ next add goes here O(1)
When full → allocate 2x, copy all → O(n)
Amortized per append: O(1)
val list = mutableListOf(10,20,30)
list.add(40) // O(1) append
list.addAll(listOf(50,60))
list.add(0, 5) // O(n) insert at 0
list.removeAt(0) // O(n) shift
list.removeLast() // O(1) pop
list.removeAll { it > 50 } // bulk remove
list.retainAll { it % 10 == 0 }
// Safe variants (null if empty)
list.removeLastOrNull()
list.removeFirstOrNull()
// View (backed by original list)
list.subList(1, 3) // [from, to)
// Kotlin DSL builder
val built = buildList { add(1); add(2) }
// As Stack
list.add(x) // push
list.last() // peek
list.removeLast() // pop O(1)
// As Queue → use ArrayDeque
val q = ArrayDeque<Int>()
q.addLast(x) // enqueue
q.removeFirst() // dequeue O(1)
// Create 3x4 matrix
val m = Array(3) { r -> IntArray(4) { c ->
r * 10 + c
}}
// Access: m[row][col] Dims: m.size × m[0].size
// Transpose (square, in-place)
for (r in 0 until n)
for (c in r+1 until n)
swap m[r][c] ↔ m[c][r]
// Rotate 90° CW: transpose → reverse rows
// Rotate 90° CCW: reverse rows → transpose
// Ragged (jagged) array — variable row lengths
val ragged = Array(4) { i -> IntArray(i+1) }
- Row-major traversal (outer=rows) is cache-friendly; column-major causes cache misses
- Spiral order: 4 boundaries
top, bottom, left, right — shrink inward
- Deep copy:
Array(n) { original[it].copyOf() } — .copyOf() on 2D is shallow!
- Ragged arrays: rows can differ in length — check
m[r].size per row
Sorting Algorithms
O(n²) avg/worst / O(n) best / O(1) / stable
Repeatedly swap adjacent elements if out of order.
Largest element "bubbles up" to the end each pass.
[5 1 4 2 8] → swap 5,1
[1 5 4 2 8] → swap 5,4
[1 4 5 2 8] → swap 5,2
[1 4 2 5 8] → 5,8 ok. 8 is sorted.
Repeat for remaining n-1 elements...
- Early exit optimization: if no swaps occur in a pass, the array is already sorted → O(n) best case
- Stable — equal elements maintain original order
- Simple to understand and implement, but O(n²) makes it impractical for large inputs
- Useful mainly for teaching — demonstrates the concept of sorting by local swaps
▶ Visualize
O(n²) always / O(1) / unstable
Find the minimum in the unsorted region, swap it to the front.
[64 25 12 22 11] min=11
[11|25 12 22 64] min=12
[11 12|25 22 64] min=22
[11 12 22|25 64] min=25
[11 12 22 25 64] done
↑sorted|unsorted↑
- Always O(n²) — no early exit, scans the entire unsorted region every pass
- Minimum swaps (n-1) — useful when writes are expensive (e.g., flash memory, EEPROM)
- Unstable — swapping can change relative order of equal elements
- Simple and predictable, but outperformed by insertion sort on nearly sorted data
▶ Visualize
O(n²) worst / O(n) best / O(1) / stable
Take the next element, insert into its correct position
in the sorted prefix by shifting larger elements right.
[5|1 4 2 8] insert 1 → shift 5
[1 5|4 2 8] insert 4 → shift 5
[1 4 5|2 8] insert 2 → shift 5,4
[1 2 4 5|8] insert 8 → already ok
[1 2 4 5 8] done
- Best case O(n) for nearly sorted data — only compares, no shifts needed
- Stable — preserves relative order of equal elements
- Online — can sort as data arrives (don't need the full input upfront)
- Used by TimSort for small subarrays (<64 elements) due to low overhead
- Best O(n²) sort in practice — outperforms bubble and selection on real data
▶ Visualize
O(n log n) / O(n) / stable
Divide in half, sort each, merge:
[38 27 43 3 9 82 10]
[38 27 43 3] [9 82 10]
[38 27] [43 3] [9 82] [10]
[27 38] [3 43] [9 82] [10] merge pairs
[3 27 38 43] [9 10 82] merge halves
[3 9 10 27 38 43 82] final merge
log n levels × O(n) merge per level = O(n log n)
- Stable — equal elements maintain original order (critical for multi-key sorts)
- Guaranteed O(n log n) — no worst-case degradation unlike Quick Sort
- Needs O(n) extra space for the merge buffer — main downside
- Excellent for linked lists (merge is O(1) space with pointer manipulation)
- Merge step pattern reused in: merge two sorted arrays, count inversions, external sort
▶ Visualize
O(n log n) avg / O(n²) worst / O(log n) / unstable
Pick pivot, partition, recurse:
[3 6 8 10 1 2 1] pivot=6
[3 1 2 1] 6 [8 10] partition around 6
↓ recurse ↓ recurse
[1 1 2 3] 6 [8 10]
[1 1 2 3 6 8 10]
Partition: two-pointer scan, swap elements
to correct side of pivot. O(n) per level.
Avg log n levels → O(n log n)
Worst (already sorted + bad pivot) → O(n²)
- In-place — only O(log n) stack space. Faster constant than Merge Sort in practice
- Pivot choice matters: median-of-three or random pivot avoids O(n²) worst case
- 3-way partition (Dutch National Flag) handles many duplicates efficiently
- Partition step is the foundation of Quick Select (kth element in O(n) avg)
- Kotlin/JVM uses Dual-Pivot Quicksort for primitive arrays
▶ Visualize
O(n log n) guaranteed / O(1) / unstable
Build a max-heap, then repeatedly extract the maximum.
Phase 1: Build max-heap in O(n)
heapify from last internal node upward
[4 10 3 5 1] → [10 5 3 4 1] (max-heap)
Phase 2: Extract max n times
swap root ↔ last, shrink heap, sift down
[10 5 3 4 1] → swap → [1 5 3 4|10]
sift down 1 → [5 4 3 1|10] → extract 5...
- O(n log n) guaranteed — no worst-case degradation, unlike Quick Sort
- In-place (O(1) extra space) — the only comparison sort that is both in-place and worst-case optimal
- Unstable — heap extraction swaps distant elements, breaking relative order
- Poor cache locality — parent/child index jumps cause cache misses; slower in practice than TimSort
- Useful when you need guaranteed performance with no extra memory
▶ Visualize
Non-Comparison Sorts
O(n+k) / O(k) / stable — k = range of values
Count frequency of each value, then place directly:
input: [4 2 2 8 3 3 1]
Step 1: count frequencies
idx: 1 2 3 4 ... 8
cnt: 1 2 2 1 1
Step 2: prefix sums (cumulative counts)
Step 3: place elements right-to-left (stable)
output: [1 2 2 3 3 4 8]
- Not comparison-based — bypasses the Ω(n log n) lower bound for comparison sorts
- O(n + k) — linear when k (value range) is O(n). Impractical when k is huge
- Stable — right-to-left placement preserves relative order of equal elements
- Building block for Radix Sort (counting sort applied per digit)
- Only works for non-negative integers (or values mappable to small integer keys)
▶ Visualize
O(d·(n+k)) / O(n+k) / stable — d=digits, k=base
Sort by each digit position (LSD → MSD) using a stable sort:
[170 45 75 90 802 24 2 66]
ones: [170 90 802 2 24 45 75 66]
tens: [802 02 24 45 66 170 75 90]
hunds: [2 24 45 66 75 90 170 802]
- LSD (Least Significant Digit first) — process ones, tens, hundreds... using counting sort at each level
- O(d × n) when base k is constant — linear for fixed-width integers (d ≤ 10 for 32-bit ints)
- Stable — each digit pass preserves the ordering from previous passes
- Works for integers and fixed-length strings. Not for variable-length or floating-point
- Can beat comparison sorts when d is small (e.g., sorting 1 million 6-digit numbers)
▶ Visualize
O(n+k) avg / O(n²) worst / O(n) / stable
Distribute elements into buckets, sort each bucket, concatenate:
[0.78 0.17 0.39 0.26 0.72 0.94]
B0:[0.17] B2:[0.26 0.39]
B7:[0.72 0.78] B9:[0.94]
Sort each bucket (insertion sort)
Concatenate: [0.17 0.26 0.39 0.72 0.78 0.94]
- O(n + k) average when input is uniformly distributed across buckets
- O(n²) worst case — all elements land in one bucket → falls back to insertion sort
- Best for uniformly distributed floating-point values in a known range
- Number of buckets k is typically chosen as n (one element per bucket on average)
When to Use
uniform float distributionWhy: When input values are uniformly distributed in a known range (e.g., [0, 1)), elements spread evenly across buckets, giving O(n) average time — the ideal case for bucket sort.
scatter-gather sortingWhy: The distribute-sort-merge pattern (scatter into buckets, sort each, gather results) naturally parallelizes and works well when data can be partitioned into independent ranges.
▶ Visualize
| Algorithm |
Best |
Average |
Worst |
Space |
Stable |
Notes |
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Early exit if no swaps; educational only |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No | Minimum swaps (n-1); always O(n²) |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Best for nearly sorted & small arrays; online |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Guaranteed; great for linked lists |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Fastest in practice; pivot choice critical |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | In-place guaranteed; poor cache locality |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes | k = value range; integers only |
| Radix Sort | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k) | Yes | d = digits; uses counting sort per digit |
| Bucket Sort | O(n+k) | O(n+k) | O(n²) | O(n) | Yes | Uniform distribution required |
| Tim Sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | Kotlin/JVM default for objects; hybrid merge+insertion |
Algorithm Patterns — Pointer & Window
arr: [1 3 5 7 9 11] target = 12
L→ ←R
sum = 1+11 = 12 ✓ found
sum < target → L++
sum > target → R--
When to Use
two sum (sorted)Why: Sorted order means L+R too small → L++, too big → R--. Eliminates brute-force O(n²) pair scanning into a single O(n) pass from both ends.
valid palindromeWhy: Symmetric structure — compare char at L with char at R, move inward. If they always match, it's a palindrome. Natural fit for converging pointers.
container with most waterWhy: Width decreases as pointers converge, so you must move the shorter wall inward — it's the only pointer that could yield a taller container. Greedy + convergent.
3SumWhy: Fix one element, then two-pointer the sorted remainder. Sorting enables skipping duplicates and the L/R convergence reduces the inner loop from O(n) brute-force to O(n) two-pointer.
squares of sorted arrayWhy: Negative numbers have large squares on the left, positives on the right. Converge from both ends, picking the larger square each step into a result array. Single pass O(n).
- Requires sorted input (or symmetric structure like palindrome)
- Start
L=0, R=lastIndex, move inward based on comparison
- 3Sum: fix one element, two-pointer on remainder — O(n²)
- Skip duplicate values to avoid repeated results
▶ Visualize
Remove duplicates from sorted:
[0 0 1 1 1 2 2 3]
S F nums[F]≠nums[S]
→ S++, write nums[F]
result: [0 1 2 3 ...]
slow = write head
fast = read head
When to Use
remove duplicatesWhy: Sorted input means dupes are adjacent. Slow pointer marks the write head; fast pointer scans. When fast finds a new value, write it at slow. No extra space needed.
move zerosWhy: Slow pointer tracks where the next non-zero should go. Fast scans all elements. Non-zeros get written at slow; remaining slots are filled with zeros. In-place, order-preserving.
partition arrayWhy: Need to rearrange elements by a condition (e.g., negatives before positives) without extra space. Slow marks the boundary, fast scans and swaps qualifying elements forward.
remove elementWhy: "Remove element" or "keep only matching" — fast reads every element, slow only advances when an element passes the filter. Result length = slow pointer position.
merge sorted array in-placeWhy: Two sorted arrays, one with trailing space. Start from the ends (largest elements) and fill backwards. Both pointers move in the same direction (right to left). O(n+m) time, O(1) extra space.
string compressionWhy: Read pointer scans runs of identical chars; write pointer writes char + count. Classic slow/fast pattern where slow = compressed write position and fast = read position.
remove duplicates IIWhy: Allow at most 2 duplicates in sorted array. Same slow/fast pointers but track count of current value.
sort by parityWhy: Move even numbers to even indices, odd to odd indices. Two-pointer placement by parity.
- Slow = write position, fast = read position
- Fast scans every element; slow only advances on valid writes
- Preserves relative order of kept elements
- Returns
slow + 1 as new length
▶ Visualize
Max sum of subarray size k=3:
[2 1 5 1 3 2] window slides →
└──k──┘
slide: +incoming -outgoing
sum = sum + arr[R] - arr[R-k]
No recomputation — O(1) per slide
When to Use
max sum subarray of size KWhy: Fixed window size means each slide adds one element and removes one. Instead of recomputing the sum from scratch (O(k) per position), update incrementally in O(1).
substring of length K (no repeats)Why: Any property of a fixed-length substring can be maintained incrementally — add the incoming char's effect, remove the outgoing char's effect. One pass, O(n) total.
find all anagramsWhy: An anagram of pattern p has exactly length p. Slide a window of size |p| over s, maintaining a frequency map. When window freq matches p's freq, you found an anagram.
max points from cardsWhy: Take k cards from either end = total sum minus a window of size n-k. Slide the n-k window to find the minimum interior sum. Answer = total - minWindow. Fixed-size window trick.
grumpy bookstore ownerWhy: Customers during non-grumpy minutes are guaranteed. Slide a window of size k to find where suppressing grumpiness rescues the most extra customers. Fixed window maximizes bonus.
duplicate within K distanceWhy: Check if any value appears twice within a window of size k. Sliding window + set.
count subarrays avg >= thresholdWhy: Fixed window of size k, check if average meets threshold. Direct sliding window sum check.
- Build first window sum over indices
0..k-1
- Slide:
sum += arr[R] - arr[R-k] for R from k to n-1
- Track max/min/count as window slides
- For anagram search: compare frequency maps instead of sums
▶ Visualize
Longest substring, no repeats:
"a b c a b c b b"
L─────R expand R
L───R shrink L (dup 'a')
pattern:
expand R always
shrink L while constraint violated
update best = max(best, R-L+1)
When to Use
longest substring no repeatWhy: Window expands right greedily. When a duplicate enters, shrink left past the previous occurrence. A Set or lastSeen map tracks window contents. Each char enters/leaves once → O(n).
minimum window substringWhy: Expand right to satisfy the constraint (contain all target chars). Once satisfied, shrink left to minimize length. Frequency maps track "have" vs "need" counts.
at most K distinct charsWhy: Expand right freely. When distinct count exceeds K, shrink left until it drops back to K. A frequency map tracks counts; remove a key when its count hits zero.
min size subarray sumWhy: Expand right to grow the sum. Once sum ≥ target, shrink left to find the minimum length that still satisfies. The "satisfy then minimize" pattern of variable windows.
longest repeating char replacementWhy: Window tracks char frequencies. Valid if windowLen - maxFreq ≤ k (can replace the rest). Expand right always, shrink left when replacements exceed k. O(n) with frequency map.
fruit into baskets (2 types)Why: Longest subarray with at most 2 distinct values. Variable window with a frequency map — shrink left when distinct count exceeds 2. Same as "at most K distinct" with K=2.
longest subarray sum <= targetWhy: Shrink window when sum exceeds target. Variable-size window with sum constraint.
max ones (K flips)Why: Longest subarray of 1s if you can flip at most k 0s. Track zero count in window.
- Expand R greedily, shrink L when constraint breaks
- Use
HashMap<Char, Int> or Set to track window contents
- Each element enters and leaves window at most once → O(n)
lastSeen map lets L jump directly past duplicate
▶ Visualize
Prefix & Aggregate Patterns
nums: [1 3 5 7 9 11]
prefix: [0 1 4 9 16 25 36]
rangeSum(1,3) = prefix[4] - prefix[1]
= 16 - 1 = 15 (3+5+7)
→ O(1) per query
prefix[i+1] = prefix[i] + nums[i] | rangeSum(L,R) = prefix[R+1] - prefix[L]
When to Use
range sum queryWhy: Pre-build cumulative sums once O(n). Then any range [L,R] sum is prefix[R+1]-prefix[L] in O(1). Turns repeated O(n) queries into O(1) each.
subarray sum equals KWhy: If prefixSum[j] - prefixSum[i] = k, then subarray [i,j) sums to k. Store prefix sum counts in a HashMap — check if (currentSum - k) was seen before. O(n) total.
product except selfWhy: Left-prefix product gives product of all elements left of i. Right-suffix product gives all right of i. Multiply them for the answer. Avoids division, handles zeros.
2D matrix region sumWhy: Extension to 2D: build a prefix sum matrix using inclusion-exclusion. Any rectangle sum becomes O(1) with four lookups: add, subtract overlaps, add back double-subtracted corner.
find pivot indexWhy: Find index where left sum equals right sum. Total prefix sum lets you check leftSum == totalSum - leftSum - nums[i] at each index in O(1). Single pass after prefix build.
contiguous array (0s and 1s)Why: Replace 0→-1, then longest subarray with sum 0 = equal 0s and 1s. Use prefix sum + HashMap: if same prefix sum seen before, the subarray between is balanced.
- Subarray sum = k: store prefix counts in HashMap; check
currentSum - k
- Product except self: left-prefix product × right-suffix product
- 2D: inclusion-exclusion:
dp[r2][c2] - dp[r1][c2] - dp[r2][c1] + dp[r1][c1]
- Prefix array is size
n+1 with prefix[0] = 0
▶ Visualize
Maximum subarray sum:
[-2 1 -3 4 -1 2 1 -5 4]
└─── max = 6 ───┘
at each i:
current = max(nums[i], current + nums[i])
best = max(best, current)
"extend or restart" — if running sum
goes negative, start fresh at nums[i]
maxEndingHere(i) = max( nums[i], maxEndingHere(i-1) + nums[i] )
When to Use
maximum subarray sumWhy: At each position, decide: extend the current subarray or start fresh. If the running sum goes negative, it can only hurt future elements — restart. Greedy DP in O(n).
max circular subarrayWhy: A wrapping subarray = total sum minus the minimum subarray in the middle. Run Kadane's for both max and min subarrays. Answer = max(standard, total - minSubarray).
max subarray with indicesWhy: Same Kadane's logic, but track currStart (reset when restarting) and update bestStart/bestEnd when a new best is found. Indices come for free from the extend-or-restart decision.
best time to buy/sell stockWhy: Track minimum price so far (buy point). At each price, profit = price - minSoFar. Same "extend or restart" idea — if price drops below minSoFar, reset the buy point.
maximum product subarrayWhy: Track both max and min running product (a negative min can flip to max). At each element: newMax = max(num, maxProd*num, minProd*num). Kadane's variant with min/max tracking.
- Initialize:
best = current = nums[0]
- Circular variant: answer = max(standard Kadane, totalSum - minSubarray)
- Track
currStart; update bestStart, bestEnd when current > best
- If all negative: returns the least-negative element
▶ Visualize
Search & Partition Patterns
Find 7 in sorted array:
[1 3 5 7 9 11 13]
L M R
mid = L + (R-L)/2 ← avoids overflow
nums[M] == target → return M
nums[M] < target → L = M+1
nums[M] > target → R = M-1
When to Use
find target in sorted arrayWhy: Sorted = monotonic. Compare middle element to target: if smaller, discard left half; if larger, discard right half. Halves the search space each step → O(log n).
first & last positionWhy: Standard binary search stops at any match. To find the first: on match, record it but keep searching left (R=mid-1). For last: keep searching right (L=mid+1). Same O(log n).
search in rotated arrayWhy: A rotated sorted array has two sorted halves. At each step, determine which half is sorted (compare L to mid). If target falls in the sorted range, search there; otherwise search the other half.
search on answer (Koko eating bananas)Why: When the answer space is monotonic ("is X feasible?" flips from false→true), binary search over the answer itself. Test the midpoint with a feasibility check. Parametric search pattern.
peak elementWhy: Not fully sorted, but locally monotonic. If mid < mid+1, a peak exists to the right; otherwise to the left. Binary search on slope direction finds any peak in O(log n).
koko eating bananasWhy: Classic "search on answer" — binary search over eating speed k. For each k, check if Koko finishes in time (feasibility = O(n)). Monotonic: higher speed always finishes faster. O(n log max).
capacity to ship within D daysWhy: Binary search on capacity [max(w)..sum(w)]. For each candidate, greedily pack weights into days. Monotonic: higher capacity always needs fewer days. O(n log sum).
search insert positionWhy: Find index where target would be inserted in sorted array. Classic binary search returning lo when not found.
- Find first: on match, set
result=mid; R=mid-1 (keep searching left)
- Find last: on match, set
result=mid; L=mid+1 (keep searching right)
- Rotated: determine which half is sorted; narrow accordingly
- Parametric: binary search on the answer — "min X s.t. predicate(X) is true"
- Kotlin stdlib:
arr.binarySearch(target) — returns -(insertionPoint)-1 if not found
▶ Visualize
3-way partition (0s, 1s, 2s):
before: [2 0 2 1 1 0 0 2 1]
after: [0 0 0 1 1 1 2 2 2]
low mid high
invariants at each step:
arr[0..low-1] = all 0s
arr[low..mid-1] = all 1s
arr[mid..high] = unexplored
arr[high+1..n-1] = all 2s
When to Use
sort colors (0,1,2)Why: Only 3 distinct values — don't need a full sort. Three pointers carve out regions for 0s, 1s, and 2s in a single pass. O(n) time, O(1) space — faster than O(n log n) sort.
three-way partitionWhy: Generalization: any time you need to split elements into exactly 3 groups (less than, equal to, greater than a pivot) in one pass. Used in quicksort optimization for duplicate-heavy data.
partition around pivotWhy: Elements < pivot go left, = pivot stay middle, > pivot go right. The three-pointer invariant ensures each element is examined at most once. Foundation of quicksort's partition step.
sort array by parityWhy: Two categories (even/odd) = simplified Dutch flag with just 2 groups. One pointer tracks the boundary, other scans — swap evens to the front. Single pass, O(1) space.
negatives / zeros / positivesWhy: Three-way partition variant: group negatives, zeros, and positives. Same lo/mid/hi pointer technique.
- Three pointers:
low=0, mid=0, high=lastIndex
nums[mid]==0 → swap with low, advance bothnums[mid]==1 → just advance midnums[mid]==2 → swap with high, retreat high, don't advance mid- Single pass, in-place — no extra storage
▶ Visualize
Two approaches:
IntArray(26) ← lowercase chars only, O(1) space
freq[ch - 'a']++
HashMap<T,Int> ← any type, O(k) space
freq[x] = (freq[x] ?: 0) + 1
or groupingBy { it }.eachCount()
When to Use
anagram checkWhy: Anagrams have identical character frequencies. Count chars for string s (increment), then for string t (decrement). If all counts are zero, they're anagrams. O(n) time, O(1) space for fixed alphabet.
first non-repeating elementWhy: First pass: build frequency map. Second pass: scan left-to-right, return first char with count=1. Two O(n) passes. The map lets you check uniqueness in O(1) per char.
majority element (Boyer-Moore)Why: Boyer-Moore Voting: maintain a candidate and count. Same element → count++, different → count--. When count hits 0, switch candidate. The majority element survives all cancellations. O(1) space.
character frequency countWhy: Count occurrences of each character/element. Foundation for anagram checks, frequency-based problems.
group anagramsWhy: All anagrams share the same sorted-character key (or frequency signature). Use that as a HashMap key to bucket strings. O(n·k) where k = avg string length.
top-K frequent elementsWhy: Build frequency map in O(n), then extract top K by sorting entries by count or using a min-heap of size K. The counting step is the core — heap/sort is just the extraction.
- Anagram: increment for s, decrement for t — all zeros = anagram
- First unique: freq pass, then scan for
freq[ch] == 1
- Boyer-Moore Voting: O(1) space for majority element — cancel non-matching pairs
- Group anagrams: sorted chars or freq signature as map key
- Kotlin:
s.groupingBy { it }.eachCount() — one-liner frequency map
▶ Visualize
Next Greater Element:
temps: [73 74 75 71 69 72 76 73]
stack: [indices of unresolved elements]
Process 72 (idx 5):
stack has [75,71,69] → pop 69,71 (< 72)
answer[4]=72, answer[3]=72, push 72
Process 76 (idx 6):
stack has [75,72] → all < 76
pop 72 → answer[5]=76 ✓
pop 75 → answer[2]=76 ✓
push 76
Maintain: decreasing stack for "next greater"
increasing stack for "next smaller"
Each element pushed/popped at most once → O(n)
When to Use
next greater elementWhy: For each element, you need the first larger element to its right. A decreasing stack keeps candidates. When a new element is larger than the top, it's the answer for all smaller tops — pop and record. O(n) total since each index is pushed/popped once.
daily temperaturesWhy: "How many days until warmer?" = next greater element by index difference. Stack stores indices of unresolved days. When a warmer day arrives, pop all cooler days and compute the gap.
trapping rain waterWhy: Water is trapped between taller bars. A decreasing stack tracks bars. When a taller bar arrives, pop shorter bars — water between the popped bar and the new taller bar fills the gap. Handles layer-by-layer.
largest rectangle in histogramWhy: For each bar, you need the nearest shorter bar on both sides. An increasing stack tracks bars. When a shorter bar arrives, popped bars can't extend further — compute their max rectangle. O(n) total.
stock span problemWhy: "How many consecutive days was price ≤ today?" = distance to previous greater element. Decreasing stack of indices; when today's price pops smaller prices, span = today - stack.top. O(n) amortized.
remove K digitsWhy: Greedily remove digits that break non-decreasing order (left to right). Monotonic increasing stack: if incoming digit < top and removals left, pop the top. Ensures the smallest remaining number.
next smaller elementWhy: Find next smaller element for each position. Monotonic increasing stack — mirror of next greater element.
- Decreasing stack: finds next greater — pop when incoming > top
- Increasing stack: finds next smaller — pop when incoming < top
- Store indices on stack (not values) for distance calculations
- Each element enters and leaves stack at most once → amortized O(n)
- Kotlin:
ArrayDeque<Int> as stack — addLast() / removeLast()
▶ Visualize
Find 2nd smallest (k=1, 0-indexed):
[3 2 1 5 6 4] pivot=5
partition →
[3 2 1 4 5 6] pivotIdx=4
k=1 < 4 → recurse LEFT [0..3]
[3 2 1 4] pivot=1
[1 2 3 4] pivotIdx=0
k=1 > 0 → recurse RIGHT [1..3]
[_ 2 3 4] pivot=3, pivotIdx=2
k=1 < 2 → recurse LEFT [1..1]
single element → answer = arr[1] = 2
When to Use
kth smallest elementWhy: Full sort is O(n log n) but you only need one element. Quick Select partitions like quicksort but recurses into only ONE side — the side containing k. Average O(n), only processes elements that could be the answer.
find medianWhy: Median = element at index n/2 in sorted order. Quick Select finds this in O(n) average without sorting the entire array. Much faster than O(n log n) full sort for a single order statistic.
top-K elementsWhy: After Quick Select places the kth element correctly, all elements left of k are smaller (unsorted). You get the top-K partition in O(n) average — then sort just those K elements if order matters.
kth largest in streamWhy: Maintain a min-heap of size k. Each new element: if larger than heap root, replace root and heapify. Root is always the kth largest. O(n log k) total, O(k) space. Quick Select variant for static arrays.
- Like quicksort but only recurse into one partition
- Average O(n), worst O(n²) — use random pivot to avoid worst case
- Partition places pivot at its final sorted position
- If pivotIdx == k → found! If k < pivotIdx → go left, else go right
- Median of Medians: guarantees O(n) worst case (rarely needed in practice)
▶ Visualize
Place each number at its correct index:
Array contains values 1..n (or 0..n-1)
[3 1 5 4 2] nums[0]=3 → should be at idx 2
swap nums[0] ↔ nums[2]
[5 1 3 4 2] nums[0]=5 → should be at idx 4
swap nums[0] ↔ nums[4]
[2 1 3 4 5] nums[0]=2 → should be at idx 1
swap nums[0] ↔ nums[1]
[1 2 3 4 5] all in place!
Rule: while nums[i] ≠ i+1 → swap to correct spot
After sorting: missing/duplicate = index mismatch
When to Use
find missing numberWhy: Array has values in range [0,n] or [1,n] — each value has a "home" index. Place each number at its home, then scan for the index where nums[i] ≠ expected. That index reveals the missing number. O(n) time, O(1) space.
find all duplicatesWhy: Place each number at index (val-1). If nums[target] already equals the value, it's a duplicate. After one pass of cyclic placement, scan for mismatches — each mismatch is a duplicate. No extra space needed.
first missing positiveWhy: Ignore negatives and values > n. Place valid positives at index (val-1). After placement, the first index where nums[i] ≠ i+1 gives the first missing positive. O(n) time, O(1) space — the optimal solution.
find corrupt pairWhy: One number duplicated, one missing (corrupt sequence). Cyclic sort places numbers at home indices. The index with a wrong number reveals both: the wrong number is the duplicate, and (index+1) is the missing one.
sort 1-to-N in placeWhy: Place each value v at index v-1. The foundational cyclic sort operation that enables missing/duplicate detection.
- Key insight: values in range [1,n] → value
v belongs at index v-1
- Swap loop:
while (nums[i] != i + 1) swap(nums[i], nums[nums[i] - 1])
- Skip if nums[i] == nums[target] (already placed or duplicate)
- Each number moves at most once to its home → O(n) total swaps
- After sorting: scan for
nums[i] != i + 1 to find anomalies
▶ Visualize
Rotation & Interval Patterns
Rotate right by k=3 (triple reversal):
[1 2 3 4 5 6 7] original
[7 6 5 4 3 2 1] 1. reverse all
[5 6 7 4 3 2 1] 2. reverse [0..k-1]
[5 6 7 1 2 3 4] 3. reverse [k..n-1]
When to Use
rotate right by KWhy: Triple reversal trick: reverse all, reverse first k, reverse rest. Each reversal is O(n) in-place. Avoids the naive O(n·k) approach of shifting one position at a time, and uses O(1) extra space.
reverse a portionWhy: Reverse a subarray between two indices. Building block for rotation and word reversal algorithms.
reverse words in stringWhy: Reverse the entire string, then reverse each word individually. The double reversal cancels out within each word but flips word order. Classic in-place string manipulation using the same reversal primitive.
matrix rotate 90°Why: Transpose (swap rows↔cols) then reverse each row = 90° clockwise. Both operations are in-place O(n²). Decomposing rotation into two simple transforms avoids complex index mapping.
next permutationWhy: Find rightmost ascending pair (i, i+1), swap nums[i] with the smallest larger element to its right, then reverse the suffix. Uses the reversal primitive for the final step. O(n) in-place.
spiral matrixWhy: Traverse matrix in spiral order by maintaining top/bottom/left/right boundaries. After each row/column traversal, shrink the corresponding boundary. Reversal/rotation thinking helps with direction changes.
- Handle
k = k % n (k can be > array length)
- Reverse entire array
- Reverse first k elements
- Reverse remaining n-k elements
- Rotate left by k = rotate right by
n - k
- Reverse words: reverse entire string, then reverse each word individually
- Matrix 90° CW: transpose then reverse each row
▶ Visualize
Sort by start, then merge overlapping:
input: [1,3] [2,6] [8,10] [15,18]
1━━━3
2━━━━━6 overlap → extend
8━━10
15━━18
output: [1,6] [8,10] [15,18]
merge if: current.start <= last.end
extend: last.end = max(last.end, current.end)
When to Use
merge overlapping intervalsWhy: Sorting by start time groups overlapping intervals adjacently. Then a single greedy pass merges: if current.start ≤ last.end, they overlap — extend. Otherwise, start a new group. O(n log n) for sort.
insert intervalWhy: Already sorted list: add all intervals before the new one, merge all that overlap with it, then add all after. Three phases, single pass O(n). Sorting is already done.
meeting roomsWhy: Sort start times and end times separately. Sweep through starts: if a meeting starts before the earliest ending, you need another room. Otherwise, reuse a freed room. Counts peak overlap.
employee free timeWhy: Merge all busy intervals, then the gaps between merged intervals are the free slots. Same merge pattern, just extract the complement. Sort + merge + gap extraction.
non-overlapping intervalsWhy: Minimum removals to eliminate all overlaps. Sort by end time, greedily keep intervals that don't overlap with the last kept. Count of removed = total - kept. O(n log n).
minimum meeting roomsWhy: Sort arrival and departure times separately. Sweep through arrivals: if an arrival comes before the earliest departure, need another platform. Same as meeting rooms — count peak concurrency.
- Always sort by start time first
- Insert: add before, merge overlapping, add after — O(n)
- Meeting rooms: sort starts and ends separately; count overlapping starts before each end
- Overlap test:
current[0] <= last[1]
▶ Visualize
Common Pitfalls & Gotchas
// WRONG: last index is size-1, not size
arr[arr.size] // ArrayIndexOutOfBoundsException
// RIGHT:
arr[arr.lastIndex] // or arr[arr.size - 1]
// WRONG: binary search overflow
val mid = (lo + hi) / 2 // can overflow!
// RIGHT:
val mid = lo + (hi - lo) / 2
// WRONG: sum overflows Int
arr.sum()
// RIGHT: use Long accumulator
arr.fold(0L) { acc, v -> acc + v }
// WRONG: == compares REFERENCES on arrays!
intArrayOf(1,2) == intArrayOf(1,2) // false!
// RIGHT: use contentEquals
intArrayOf(1,2).contentEquals(intArrayOf(1,2))
Quick Reference
| Algorithm |
Time |
Space |
Key Requirement |
| Two Pointers (convergent) | O(n) | O(1) | Sorted array or symmetric structure |
| Two Pointers (same-dir) | O(n) | O(1) | In-place read/write partitioning |
| Sliding Window (fixed) | O(n) | O(1) | Subarray of fixed length k |
| Sliding Window (variable) | O(n) | O(k) | Constraint-based window expansion |
| Prefix Sum (build) | O(n) | O(n) | Range queries needed after build |
| Prefix Sum (query) | O(1) | — | After O(n) preprocessing |
| Kadane's Algorithm | O(n) | O(1) | Contiguous subarray optimization |
| Binary Search | O(log n) | O(1) | Monotonic / sorted search space |
| Dutch National Flag | O(n) | O(1) | 3-way partitioning (3 distinct groups) |
| Frequency Counting | O(n) | O(k) | Count distinct elements (k = distinct) |
| Array Rotation | O(n) | O(1) | Triple reversal trick |
| Merge Intervals | O(n log n) | O(n) | Sort dominates; greedy merge |
| Monotonic Stack | O(n) | O(n) | Next greater/smaller element queries |
| Quick Select | O(n) avg | O(1) | Kth element without full sort |
| Cyclic Sort | O(n) | O(1) | Values in range [1,n] or [0,n-1] |
| If You See... | Try This |
|---|
| "sorted array" + pair/triplet | Two Pointers (converge) |
| "in-place" + remove/filter | Two Pointers (same-dir) |
| "subarray of size k" | Sliding Window (fixed) |
| "longest/shortest with constraint" | Sliding Window (variable) |
| "range sum" or "subarray sum = k" | Prefix Sums + HashMap |
| "max contiguous subarray" | Kadane's |
| "sorted" + "find" or "min X s.t." | Binary Search |
| "partition into 3 groups" | Dutch National Flag |
| "anagram" / "frequency" / "unique" | Frequency Counting |
| "rotate" / "reverse words" | Triple Reversal |
| "overlapping intervals" | Sort + Merge Intervals |
| "next greater" / "next warmer" | Monotonic Stack |
| "kth largest" / "median" / "top K" | Quick Select |
| "missing number" in range [1,n] | Cyclic Sort |
| "histogram" / "trapping rain water" | Monotonic Stack |
Data Structure Operations
| Operation |
IntArray |
MutableList |
ArrayDeque |
| Access by index | O(1) | O(1) | O(1) |
| Update by index | O(1) | O(1) | O(1) |
| Append to end | N/A (fixed) | O(1) amortized | O(1) amortized |
| Prepend to front | N/A (fixed) | O(n) shift | O(1) amortized |
| Insert at index | N/A (fixed) | O(n) shift | O(n) shift |
| Delete at index | N/A (fixed) | O(n) shift | O(n) shift |
| Linear search | O(n) | O(n) | O(n) |
| Binary search (sorted) | O(log n) | O(log n) | — |
| Sort | O(n log n) | O(n log n) | — |