DSA

Top DSA Interview Problems

High-frequency problems with pattern tags, approach hints, and complexity — your prioritized study list.

Interview tip For each problem: pattern → brute force → optimized → complexity → edge cases (empty, single, duplicates).

① Arrays & hashing — top problems

Problem	Pattern	Approach hint	Complexity
Two Sum	Hash map	Store complement as you scan	O(n) time O(n) space
3Sum	Sort + two pointers	Fix i, two-pointer rest for zero sum	O(n²)
Container With Most Water	Two pointers	Move shorter line inward	O(n)
Longest Substring Without Repeating	Sliding window	Map char → last index; shrink on dup	O(n)
Product of Array Except Self	Prefix/suffix	Output[i] = left product × right product	O(n) O(1)* extra
Merge Intervals	Sort + merge	Sort by start; merge overlaps	O(n log n)
Trapping Rain Water	Two pointers / stack	Max left/right height at each index	O(n)

Problem	Pattern	Approach hint	Complexity
Reverse Linked List	In-place reversal	prev/curr/next iteration	O(n) O(1)
Merge Two Sorted Lists	Dummy head	Compare heads, attach smaller	O(n+m)
Linked List Cycle	Fast/slow	Floyd detection	O(n) O(1)
Reorder List	Multi-step	Find middle, reverse 2nd half, merge	O(n)
LRU Cache	HashMap + DLL	Get/put O(1); evict tail on capacity	O(1) per op

LRU Cache is a design + DSA favorite — practice implementing from scratch.

Problem	Pattern	Approach hint	Complexity
Invert Binary Tree	DFS/BFS	Swap children recursively	O(n)
Validate BST	DFS bounds	Pass (min, max) down	O(n)
Lowest Common Ancestor	DFS	Return node if p/q found in subtrees	O(n)
Binary Tree Level Order	BFS	Queue per level	O(n)
Serialize/Deserialize BT	BFS/DFS	Include null markers	O(n)
Number of Islands	DFS/BFS grid	Mark visited; flood fill	O(m×n)
Course Schedule	Topo sort	Kahn or cycle detect DFS	O(V+E)
Word Ladder	BFS	Bidirectional BFS optional	O(N×L²)

Problem	Pattern	State / recurrence	Complexity
Climbing Stairs	1D DP	dp[i]=dp[i-1]+dp[i-2]	O(n) O(1)
House Robber	1D DP	dp[i]=max(dp[i-1], nums[i]+dp[i-2])	O(n)
Coin Change	Unbounded knapsack	dp[a]=min coins for amount a	O(amount×coins)
Longest Increasing Subsequence	DP or patience	O(n²) DP or O(n log n) binary search on tails
Word Break	String DP	dp[i]=true if prefix breakable	O(n²×dict)
Edit Distance	2D string DP	Insert/delete/replace min ops	O(m×n)
Unique Paths	Grid DP	dp[r][c]=dp[r-1][c]+dp[r][c-1]	O(m×n)

Problem	Pattern	Key idea
Kth Largest Element	Min-heap size K	Or quickselect O(n) avg
Merge K Sorted Lists	Min-heap of heads	Pop min, push next from that list
Find Median from Data Stream	Two heaps	Balance sizes after each add
Top K Frequent Elements	Heap or bucket sort	Bucket by frequency O(n)
Task Scheduler	Greedy + math	Cooldown slots or heap simulation

Problem	Search space	Predicate
Search in Rotated Sorted Array	Index	Which half is sorted?
Find Minimum in Rotated Sorted Array	Index	Compare mid with right
Koko Eating Bananas	Speed k	Can finish in H hours?
Median of Two Sorted Arrays	Partition i	Left parts ≤ right parts

Quality > quantity: 50 well-understood problems beat 200 shallow solves.

Week	Focus	Problems (daily 2)
Week 1	Arrays, hash, two pointers	Two Sum, 3Sum, Container, Longest Substring, Merge Intervals
Week 1	Trees BFS/DFS	Invert, Validate BST, LCA, Level Order
Week 2	Graphs + topo	Islands, Course Schedule, Word Ladder
Week 2	DP + heap	Coin Change, LIS, LRU Cache, Kth Largest

Structure	Access	Search	Insert	Delete
Array	O(1)	O(n)	O(n)	O(n)
Hash map	—	O(1)*	O(1)*	O(1)*
Balanced BST	O(log n)	O(log n)	O(log n)	O(log n)
Heap	min/max O(1)	—	O(log n)	O(log n)

arraystreesgraphsDPheapinterview