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! 🚀