Algorithmic Philosophy
Computer science is fundamentally the engineering of trade-offs. Every data structure represents a deliberate exchange of memory space for execution time. When you prepare for algorithm exams or technical coding interviews, stop attempting to memorize hundreds of code snippets. Master the underlying spatial mental models.
1. The Big-O Time & Space Complexity Master Chart
Before writing any algorithmic solution, you must determine whether your proposed approach will execute within standard online judge time limits (typically ~108 operations per second):
| Data Structure / Algorithm | Average Access / Search | Average Insert / Delete | Worst Case Space Complexity | Optimal Use Case |
|---|---|---|---|---|
| Array / Dynamic Vector | O(1) Access; O(n) Search | O(1) Amortized Append; O(n) Middle | O(n) contiguous RAM | Cache-friendly sequential reading and random indexing by index. |
| Hash Map / Hash Table | O(1) Average; O(n) Worst (Collisions) | O(1) Average Insert/Delete | O(n) with load factor overhead | Instant key-value lookups, counting frequency, memoization caches. |
| Self-Balancing BST (AVL / Red-Black) | O(log n) Search | O(log n) Insert / Delete | O(n) pointer overhead | Maintaining sorted order dynamically; range queries. |
| Min / Max Binary Heap (Priority Queue) | O(1) Peek Top; O(n) Arbitrary Search | O(log n) Push / Pop | O(n) array-backed | Dijkstra's shortest path, finding top K elements, event schedulers. |
2. Graph Traversal: BFS vs. DFS Intuition
Virtually all graph problems—from dependency resolution to social network distance—reduce to Breadth-First Search (BFS) or Depth-First Search (DFS):
- Breadth-First Search (BFS) [Queue / FIFO]:
Explores nodes radially outward level by level.
Rule of Thumb: Whenever a problem asks for the shortest path, minimum number of steps, or nearest neighbor in an unweighted graph, always use BFS. - Depth-First Search (DFS) [Stack / LIFO / Recursion]:
Plunges down a branch to the deepest leaf before backtracking.
Rule of Thumb: Use DFS when searching for complete combinatorial paths, detecting cycles in directed graphs, checking connectivity, or calculating topological sorts.
3. The 3-Step Dynamic Programming Intuition Framework
Dynamic Programming (DP) strikes terror into computer science students, yet it is nothing more than recursion with a memory cache. Apply this 3-step protocol:
- Step 1: Define the Subproblem State in Words:
Clearly define whatdp[i][j]represents. For example, in the classic 0/1 Knapsack problem: "dp[i][w] represents the maximum value achievable considering the first i items with a maximum weight capacity of w." - Step 2: Formulate the Recurrence Transition:
At statei, what discrete choices can you make? You can either include itemior skip itemi:dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]) - Step 3: Establish Base Cases & Iteration Order:
Initialize trivial boundary conditions:dp[0][w] = 0(zero items yield zero value) anddp[i][0] = 0(zero capacity holds zero value). Populate the 2D table bottom-up, or implement top-down recursion with a memoization hash table.