Smart: Core Interview Patterns

69 verified problems

High-frequency interview patterns (~180 problems).

Two Pointers

5 problems
Valid Palindromeeasy
TC: O(N)SC: O(1)
Two Sum II - Input Array Is Sortedmedium
TC: O(N)SC: O(1)
3Summedium
TC: O(N^2)SC: O(1)
Container With Most Watermedium
TC: O(N)SC: O(1)
Trapping Rain Waterhard
TC: O(N)SC: O(1)

Fast & Slow Pointers

5 problems
Linked List Cycleeasy
TC: O(N)SC: O(1)
Reorder Listmedium
TC: O(N)SC: O(1)
Remove Nth Node From End of Listmedium
TC: O(N)SC: O(1)
Reverse Linked Listeasy
TC: O(N)SC: O(1)
Merge Two Sorted Listseasy
TC: O(N + M)SC: O(1)

Sliding Window

5 problems
Best Time to Buy and Sell Stockeasy
TC: O(N)SC: O(1)
Longest Substring Without Repeating Charactersmedium
TC: O(N)SC: O(min(N, Sigma))
Longest Repeating Character Replacementmedium
TC: O(N)SC: O(1)
Permutation in Stringmedium
TC: O(N)SC: O(1)
Minimum Window Substringhard
TC: O(|S| + |T|)SC: O(|T|)

Binary Search on Answer

6 problems
Binary Searcheasy
TC: O(log N)SC: O(1)
Search a 2D Matrixmedium
TC: O(log(M * N))SC: O(1)
Koko Eating Bananasmedium
TC: O(N log M)SC: O(1)
Find Minimum in Rotated Sorted Arraymedium
TC: O(log N)SC: O(1)
Search in Rotated Sorted Arraymedium
TC: O(log N)SC: O(1)
Time Based Key-Value Storemedium
TC: O(log N)SC: O(N)

Top-K & Heaps

8 problems
Top K Frequent Elementsmedium
TC: O(N)SC: O(N)
Kth Largest Element in a Streameasy
TC: O(N log k)SC: O(k)
Last Stone Weighteasy
TC: O(N log N)SC: O(N)
K Closest Points to Originmedium
TC: O(N log k)SC: O(k)
Task Schedulermedium
TC: O(T)SC: O(1)
Find Median from Data Streamhard
TC: O(log N)SC: O(N)
Merge k Sorted Listshard
TC: O(N log k)SC: O(1)
LRU Cachemedium
TC: O(1)SC: O(C)

Tree Traversal & Serialization

11 problems
Invert Binary Treeeasy
TC: O(N)SC: O(H)
Maximum Depth of Binary Treeeasy
TC: O(N)SC: O(H)
Diameter of Binary Treeeasy
TC: O(N)SC: O(H)
Balanced Binary Treeeasy
TC: O(N)SC: O(H)
Same Treeeasy
TC: O(min(P, Q))SC: O(min(Hp, Hq))
Subtree of Another Treeeasy
TC: O(S * T)SC: O(Hs)
Lowest Common Ancestor of a Binary Search Treemedium
TC: O(H)SC: O(1)
Binary Tree Level Order Traversalmedium
TC: O(N)SC: O(W)
Validate Binary Search Treemedium
TC: O(N)SC: O(H)
Kth Smallest Element in a BSTmedium
TC: O(H + k)SC: O(H)
Binary Tree Maximum Path Sumhard
TC: O(N)SC: O(H)

Graph Traversal & Topological Sort

8 problems
Number of Islandsmedium
TC: O(M * N)SC: O(M * N)
Max Area of Islandmedium
TC: O(M * N)SC: O(M * N)
Clone Graphmedium
TC: O(V + E)SC: O(V)
Rotting Orangesmedium
TC: O(M * N)SC: O(M * N)
Pacific Atlantic Water Flowmedium
TC: O(M * N)SC: O(M * N)
Course Schedulemedium
TC: O(V + E)SC: O(V + E)
Course Schedule IImedium
TC: O(V + E)SC: O(V + E)
Word Ladderhard
TC: O(N * L^2)SC: O(N * L)

Union-Find

3 problems
Number of Connected Components in an Undirected Graphmedium
TC: O(V + E * a(V))SC: O(V)
Graph Valid Treemedium
TC: O(N * a(N))SC: O(N)
Longest Consecutive Sequencemedium
TC: O(N)SC: O(N)

1D DP

10 problems
Climbing Stairseasy
TC: O(N)SC: O(1)
House Robbermedium
TC: O(N)SC: O(1)
House Robber IImedium
TC: O(N)SC: O(1)
Longest Palindromic Substringmedium
TC: O(N^2)SC: O(1)
Maximum Subarraymedium
TC: O(N)SC: O(1)
Decode Waysmedium
TC: O(N)SC: O(1)
Coin Changemedium
TC: O(A * C)SC: O(A)
Maximum Product Subarraymedium
TC: O(N)SC: O(1)
Word Breakmedium
TC: O(N * W * L)SC: O(N)
Longest Increasing Subsequencemedium
TC: O(N log N)SC: O(N)

2D & Knapsack DP

8 problems
Unique Pathsmedium
TC: O(M * N)SC: O(N)
Longest Common Subsequencemedium
TC: O(M * N)SC: O(min(M, N))
Best Time to Buy and Sell Stock with Cooldownmedium
TC: O(N)SC: O(1)
Coin Change IImedium
TC: O(A * C)SC: O(A)
Target Summedium
TC: O(N * P)SC: O(P)
Interleaving Stringmedium
TC: O(M * N)SC: O(min(M, N))
Edit Distancemedium
TC: O(M * N)SC: O(N)
Longest Increasing Path in a Matrixhard
TC: O(M * N)SC: O(M * N)