Arrays & Strings Complete — 100-Problem Master Cheatsheet

Arrays & Strings — 100 Problems Complete! 🎉

Congratulations on finishing all 100 Arrays & Strings problems! This cheatsheet consolidates the key patterns so you can review quickly before interviews.

Pattern Map

Two Pointers

Problem	Pattern	Time
Two Sum (sorted)	Inward pointers	O(n)
Container with Most Water	Shrink shorter side	O(n)
Trapping Rain Water	Track left/right max	O(n)
3Sum / 4Sum	Fix outer, two pointer inner	O(n²)
Merge Sorted Array	3-pointer from end	O(m+n)

Sliding Window

Problem	Pattern	Time
Longest Substring Without Repeating	Shrinkable + set	O(n)
Min Size Subarray Sum	Shrinkable	O(n)
Max Consecutive Ones III	Count zeros	O(n)
Sliding Window Maximum	Monotonic deque	O(n)
Minimum Window Substring	have/need counter	O(n)
Subarrays with K Distinct	atMost(k)-atMost(k-1)	O(n)

Prefix Sum

Problem	Pattern	Time
Subarray Sum Equals K	prefix+hashmap	O(n)
Shortest Subarray Sum≥K	deque on prefix	O(n)
Count of Range Sum	merge sort on prefix	O(n log n)
Running Sum	cumulative	O(n)

Binary Search

Problem	Pattern	Time
Search in Rotated Array	identify sorted half	O(log n)
Find Minimum in Rotated	binary search pivot	O(log n)
Median of Two Sorted Arrays	partition search	O(log min(m,n))
Split Array Largest Sum	binary search on answer	O(n log S)
Find Peak Element	slope direction	O(log n)

Sorting / Greedy

Problem	Pattern	Time
Sort Colors	Dutch National Flag	O(n)
Merge Intervals	sort by start	O(n log n)
Non-overlapping Intervals	sort by end	O(n log n)
Partition Labels	last occurrence	O(n)
Gas Station	running tank reset	O(n)
Jump Game II	BFS levels	O(n)
Task Scheduler	frequency formula	O(n)
Candy	two-pass greedy	O(n)

Stack / Monotonic Stack

Problem	Pattern	Time
Daily Temperatures	mono-decreasing stack	O(n)
Largest Rectangle Histogram	mono-increasing stack	O(n)
Maximal Rectangle	histogram per row	O(m×n)
Longest Valid Parentheses	base-tracking stack	O(n)
Decode String	(count,str) stack	O(n)
Max Frequency Stack	freq + group stacks	O(1) per op

Backtracking

Problem	Pattern	Time
Combination Sum	pick-with-reuse	O(n^(T/m))
Permutations	swap DFS	O(n!n)
Subsets	pick/skip	O(2^n × n)
Word Search	4-dir DFS + restore	O(m×n×4^L)

In-Place / Math

Problem	Pattern	Time
Next Permutation	right-scan + suffix reverse	O(n)
Find Duplicate (Floyd)	cycle detection	O(n)
First Missing Positive	cyclic sort	O(n)
Single Number	XOR	O(n)
Missing Number	Gauss sum	O(n)
Find All Duplicates	index-negation	O(n)
Move Zeroes	write pointer	O(n)

Divide & Conquer

Problem	Pattern	Time
Count Smaller After Self	merge sort + tracking	O(n log n)
Reverse Pairs	merge sort cross-count	O(n log n)
Maximum Subarray	divide & conquer	O(n log n)

Big O Quick Reference

O(1)        → XOR, Gauss sum, Boyer-Moore, Freq-Stack ops
O(log n)    → Binary search variants
O(n)        → Two pointers, Sliding window, Monotonic stack, Prefix sum
O(n log n)  → Sort-based, Merge sort variants, Binary search + check
O(n²)       → 3Sum, 4Sum, Word Search (worst), Brute force
O(2^n × n)  → Backtracking (Subsets, Permutations)

MAANG Problem Priority

Google: Trapping Rain Water, Median Two Sorted Arrays, Sliding Window Max, Longest Consecutive, Partition Labels, Max Points on Line

Amazon: Two Sum, Sliding Window, Merge Intervals, Jump Game, Subarray Sum K, First Missing Positive, Word Search

Meta/Facebook: 3Sum, Median Two Arrays, Minimum Window Substring, Max Consecutive Ones

Microsoft: Sort Colors, Next Permutation, Find Duplicate, Daily Temperatures

Apple: Combination Sum, Subsets, Permutations, Combination Sum II

Study Schedule Recommendation

Week 1-2: Easy problems (1-25) — build intuition
Week 3-5: Medium problems (26-75) — core patterns
Week 6-8: Hard problems (76-100) — advanced techniques
Week 9+: Mock interviews, company-specific problems

Good luck with your interviews!

Key Takeaways

Arrays and strings problems decompose into ~12 core patterns: two-pointer, sliding window, prefix sum, sorting, binary search on answer, monotonic stack/deque, merge sort inversion counting, index marking, divide and conquer, greedy with heap, backtracking, and DP.
The sliding window family splits into fixed-size (use deque for max/min) and variable-size (use formed counter or frequency map); the "exactly k" variant always uses atMost(k) - atMost(k-1).
Monotonic stack reveals left/right boundaries on pop; monotonic deque maintains a running max/min in O(1) per element — these unlock Largest Rectangle, Trapping Rain Water, Sliding Window Maximum, and Jump Game VI.
"Binary search on the answer" applies whenever the answer is in a bounded range and the feasibility function is monotone — look for "minimize the maximum" or "maximize the minimum" trigger phrases.
Merge sort inversion counting (LC 315, 493, 327) counts cross-half pairs in O(n) per level; always separate the count pass from the merge pass for non-standard conditions.
Index marking (LC 41, 448, 442) uses sign negation or cyclic sort to turn the array itself into a presence map when O(1) space is required.
MAANG priority: Google favors hard geometric and DP problems; Amazon favors sliding window and greedy; Meta favors two-pointer and divide and conquer; Microsoft and Apple favor backtracking and sorting.

Arrays & Strings — 100 Problems Complete! 🎉#

Pattern Map#

Two Pointers#

Sliding Window#

Prefix Sum#

Binary Search#

Sorting / Greedy#

Stack / Monotonic Stack#

Backtracking#

In-Place / Math#

Divide & Conquer#

Big O Quick Reference#

MAANG Problem Priority#

Study Schedule Recommendation#

Key Takeaways#

Related reading