Moin Shadab — DSA Roadmap & Brain Revival

1

Big O Notation — What The Hell Is It?

🍕 The Pizza Delivery Analogy

Imagine you order pizza. How long does it take to arrive?

Big O is just a way to say: "as your input gets bigger, how much slower does your code get?"

It's not about seconds. It's about growth. Will your code be fast when there are 10 users? What about 10 million?

📊 How Fast Does It Grow? (bigger bar = slower = worse)

O(1)

O(log n)

O(n)

O(n log n)

O(n²)

O(2ⁿ)

n = input size →

📖 Every Big O — Explained Like You're 5

Notation	Name	Real World Meaning	Example
O(1)	Constant	No matter how big the input — same time. Like looking up your name in your own brain.	arr[0], HashMap lookup
O(log n)	Logarithmic	You halve the problem each step. Like finding a word in dictionary by going to middle, then middle again.	Binary Search
O(n)	Linear	Check every item once. 100 items = 100 steps. 1M items = 1M steps. Honest work.	Linear search, single loop
O(n log n)	Linearithmic	A bit worse than linear. Divide, sort pieces, combine. Like sorting a deck of cards smartly.	Merge Sort, Quick Sort
O(n²)	Quadratic	Loop inside loop. 10 items = 100 steps. 1000 items = 1,000,000 steps. Bad for big data.	Bubble Sort, nested loops
O(2ⁿ)	Exponential	DANGER. Doubles every step. Used only for small inputs. Brute force problems.	Naive recursion, subsets
O(n!)	Factorial	NIGHTMARE. All permutations. n=12 is already >400 million. Avoid unless forced.	Travelling salesman brute force

✏️ How to CALCULATE Big O in your head: 1. Drop constants: O(2n) → O(n) 2. Drop smaller terms: O(n² + n) → O(n²) 3. Count loops: one loop = O(n), nested loops = O(n²) 4. Each halving = log

2

Time vs Space vs Best/Worst Case

⏱ Time Complexity

How many steps does your code take?

Think of it as: if I give you 1000 numbers instead of 10, how many MORE operations happen?

This is what interviewers ask most. Optimize this first.

💾 Space Complexity

How much memory does your code use?

Creating a new array of size n → O(n) space. Using just a few variables → O(1) space.

Sometimes you trade space for speed. That's a valid choice.

🎭 Best Case, Worst Case, Average Case (with a human example)

Imagine you're searching for your friend "Zara" in a list of 100 names.

🟢 Best Case: Zara is the first name! You find her in 1 step → O(1)
🔴 Worst Case: Zara is last or not there at all. 100 steps → O(n)
🟡 Average Case: Usually around the middle. ~50 steps → O(n/2) = O(n)

📌 Interviewers care about Worst Case (Big O) because your system must handle the hardest scenario.

⚠️ The 3 Greek Letters you'll see: O (Big O) = Upper bound (worst case) | Ω (Omega) = Lower bound (best case) | Θ (Theta) = Tight bound (average) | In interviews: always give Big O.

3

Arrays & Strings — The Foundation

📦 What is an Array?

A box with numbered slots. [10, 20, 30, 40, 50] — slot 0 has 10, slot 1 has 20. All slots sit next to each other in memory.

Why it matters: Random access is O(1) — you can jump to any index instantly. Insertion/deletion in middle = O(n) because you shift everything.

Two Pointers

Start one pointer at left, one at right. Move them toward each other. Used for sorted arrays, pair sums, palindromes.

Easy → Medium

Sliding Window

A window of fixed or variable size that slides. Used for max sum subarray, longest substring. Turns O(n²) into O(n).

Medium

Prefix Sum

Pre-compute cumulative sums. Any subarray sum in O(1) after O(n) prep. Range queries become lightning fast.

Medium

Kadane's Algorithm

Maximum subarray sum. Track current sum and global max. One pass O(n). Classic DP-disguised-as-array problem.

Medium

HashMap Tricks

Store frequency, index, or complement. Two Sum = HashMap. Anagram check = HashMap. Most array problems have a HashMap solution.

Easy → Medium

Dutch National Flag

Sort 0s, 1s, 2s in one pass. Three pointers. Used in Quick Sort's partition step.

Medium

Operation	Array	Dynamic Array (ArrayList)
Access by index	O(1)	O(1)
Search (unsorted)	O(n)	O(n)
Insert at end	O(1) amortized	O(1) amortized
Insert at middle	O(n)	O(n)
Delete at middle	O(n)	O(n)

✓
When stuck, try sorting first — many problems become easy
✓
Two pointers → sorted array + find pair
✓
Sliding window → "consecutive", "subarray", "substring" in problem
✓
HashMap → frequency count, two sum, anagram, index tracking
✓
O(n²) solution visible? Try to reduce with two pointers or hashmap to O(n)
✓
Negative numbers in array? Be careful with sliding window — it doesn't always work

4

Linked Lists — Chains of Nodes

🔗 What is a Linked List?

Each "node" has data + a pointer to the next node. Unlike arrays, they're NOT next to each other in memory.

No random access (can't do node[3] directly — must walk from head). But insert/delete at head = O(1)!

Singly: Each node points forward only. Doubly: Points forward AND backward. Circular: Last node points back to head.

Fast & Slow Pointers

Floyd's algorithm. Fast moves 2 steps, slow moves 1 step. If they meet → cycle! Used to detect cycle, find middle node.

Medium — Very Common

Reversal

Reverse entire list or k-group. Track prev, current, next pointers. Classic interview question. Do it without extra space.

Medium

Merge Two Sorted Lists

Two pointers, compare heads, attach smaller node. Used in Merge Sort. Foundation for merging sorted arrays.

Easy

Find Nth from End

Two pointers, n apart. When fast reaches end, slow is at nth from end. One pass! No need to know length first.

Easy

🧠 Moin's Memory Trick: Whenever you see "LinkedList" in a problem — immediately think: Do I need fast/slow pointers? Do I need to reverse? Can I use a dummy head node? These 3 thoughts solve 80% of linked list problems.

5

Stacks & Queues — Push, Pop, Peek

📚 Stack — LIFO

Last In, First Out. Like a stack of plates — you add/remove from TOP only.

Push (add) → O(1) | Pop (remove) → O(1) | Peek (look) → O(1)

Used for: undo/redo, function call stack, bracket matching, DFS.

🚌 Queue — FIFO

First In, First Out. Like a bus queue — first person in line gets in first.

Enqueue (add back) → O(1) | Dequeue (remove front) → O(1)

Used for: BFS, task scheduling, sliding window maximum.

🎯 Must-Know Stack/Queue Problems

✓
Valid Parentheses — Push opening brackets, pop when closing. Mismatch = invalid. O(n)
✓
Next Greater Element — Monotonic stack. Keep decreasing stack, pop when you find greater. Classic.
✓
Min Stack — Design stack that supports getMin() in O(1). Store (val, currentMin) pairs.
✓
Sliding Window Maximum — Deque (double-ended queue). Store indices. O(n) total.
✓
Implement Queue using Stacks — Two stacks. Lazy transfer. Amortized O(1) per op.
✓
Largest Rectangle in Histogram — Monotonic stack. Hard but common in FAANG.

6

Trees — Nature's Data Structure

🌳 Binary Tree, BST, Balanced Trees

A tree is nodes connected in parent-child relationships. No cycles. One root.
Binary Tree: Each node has ≤ 2 children (left & right).
BST: Left child < parent < right child. Search = O(log n) if balanced.
Balanced (AVL, Red-Black): Keeps height O(log n) always. HashMap & TreeSet internally.

🚶 Tree Traversals — LEARN THESE COLD

// Inorder: Left → Root → Right
// Gives SORTED output for BST ✨
function inorder(node):
  if node == null: return
  inorder(node.left)
  print(node.val)
  inorder(node.right)

// Preorder: Root → Left → Right
// Used to COPY or SERIALIZE tree
function preorder(node):
  print(node.val)
  preorder(node.left)
  preorder(node.right)

// Postorder: Left → Right → Root
// Used to DELETE tree or eval expr
function postorder(node):
  postorder(node.left)
  postorder(node.right)
  print(node.val)

// Level Order (BFS)
// Level by level — use Queue!
queue.add(root)
while queue not empty:
  node = queue.poll()
  print(node.val)
  add children to queue

Height / Depth

Height = longest path to leaf. Depth = distance from root. Calculated recursively in DFS postorder.

Easy

LCA (Lowest Common Ancestor)

Find common ancestor of two nodes. In BST: compare values. In Binary Tree: recursive DFS returning nodes found.

Medium

Diameter of Tree

Longest path between any two nodes. Doesn't have to go through root! At each node: left height + right height.

Medium

Path Sum

Does a root-to-leaf path sum to target? DFS and subtract from target. At leaf, check if remaining == 0.

Easy

Serialize / Deserialize

Convert tree to string and back. Preorder with null markers. Hard but brilliant question. Tests deep understanding.

Hard

BST Validate

NOT just check left < root < right for each node. Pass min/max bounds down recursively. Classic trick.

Medium

💡 Tree Problem Template: 1. Is it asking about structure? → DFS recursion 2. Is it level by level? → BFS with queue 3. Is it BST? → Use BST properties (in-order sorted) 4. Every tree recursive function has: base case (null), left subtree, right subtree, combine result

7

Heaps & Priority Queues — Always Know the Min/Max

🏔 Heap — The "Always Sorted Top" Tree

A Min Heap: smallest element always at top. Max Heap: largest always at top.

Insert → O(log n) | Get min/max → O(1) | Extract min/max → O(log n)

Internally it's a complete binary tree stored as array. Java: PriorityQueue. Python: heapq.

Kth Largest Element

Min-heap of size k. If new element > heap top, replace. After processing all elements, top = kth largest. O(n log k)

Medium — Super Common

Top K Frequent Elements

Frequency map + min-heap. Classic pattern. Can also use bucket sort for O(n) time.

Medium

Merge K Sorted Lists

Push first element of each list into min-heap. Pop min, add its next node to heap. O(n log k) total.

Hard

Median of Data Stream

Two heaps: max-heap for lower half, min-heap for upper half. Rebalance after each insert. O(log n) insert, O(1) median.

Hard — FAANG Favorite

8

Graphs — The Most Powerful Structure

🕸 Graph = Nodes + Edges

Everything is a graph: social networks, maps, the internet, dependencies. Directed = one-way edges. Undirected = two-way. Weighted = edges have costs.

Represented as: Adjacency List (most common, O(V+E) space) or Adjacency Matrix (fast lookup, O(V²) space).

🔵 BFS — Breadth First Search ▼

Explore level by level. Uses a Queue. Finds SHORTEST PATH in unweighted graph.

Use when: shortest path, minimum steps, find all nodes at distance k, check if path exists.

visited = set()
queue = [start]
visited.add(start)
while queue not empty:
  node = queue.pop_front()
  for neighbor in graph[node]:
    if neighbor not in visited:
      visited.add(neighbor)
      queue.add(neighbor)

Time: O(V + E) | Space: O(V)

🟣 DFS — Depth First Search ▼

Go deep before going wide. Uses recursion (implicit stack) or explicit Stack. Explores one path fully before backtracking.

Use when: cycle detection, topological sort, connected components, finding all paths, maze solving.

visited = set()
function dfs(node):
  visited.add(node)
  for neighbor in graph[node]:
    if neighbor not in visited:
      dfs(neighbor)

Time: O(V + E) | Space: O(V) for call stack

🟢 Dijkstra's Algorithm — Shortest Path (Weighted) ▼

BFS but for weighted graphs. Uses a Min Heap (Priority Queue). Always process lowest-cost node next. Greedy.

Cannot handle negative weights (use Bellman-Ford for that).

Steps: 1. Put start with dist=0 in heap. 2. Pop min dist node. 3. Relax its neighbors. 4. Repeat.
Time: O((V + E) log V)

🟠 Topological Sort — Order of Dependencies ▼

Linear ordering of nodes such that for every directed edge u→v, u comes before v. Only for DAGs (Directed Acyclic Graphs).

Used for: build systems, course prerequisites, task scheduling, package dependencies.

Two methods: Kahn's Algorithm (BFS + indegree) or DFS with reverse postorder. Kahn's also detects cycles!

🔵 Union Find (Disjoint Set) — Are They Connected? ▼

Track which elements belong to the same group/component. Two operations: find(x) (which group?) and union(x,y) (merge groups).

With path compression + union by rank: nearly O(1) per operation.

Used for: detect cycle in undirected graph, number of connected components, Kruskal's MST algorithm.

9

Dynamic Programming — The Brain Buster

💡 DP in Plain English

DP = "Don't repeat your work."

If you're solving a big problem by breaking it into smaller problems — and those smaller problems repeat — save their answers instead of recalculating.

Fibonacci: fib(5) = fib(4) + fib(3). Without DP, you calculate fib(3) twice. With DP (memoization), you calculate it once and remember.

📝 Top-Down (Memoization)

Write recursion naturally. Add a cache/memo. If answer already computed — return it immediately.

memo = {}
Start recursive. Check memo first. Feels natural. Good for beginners.

📊 Bottom-Up (Tabulation)

Fill a dp table from smallest subproblem up to the answer. No recursion, no stack overflow.

Usually more efficient in practice. Looks like a loop filling a table row by row.

🗺 DP Patterns — The 7 Types (Industry Must-Know)

1D DP

dp[i] depends on dp[i-1] or earlier. Fibonacci, Climbing Stairs, House Robber.

Start Here

Knapsack (0/1)

Include or exclude each item. 2D table: items vs capacity. dp[i][w] = max value with i items, w capacity.

Medium

LCS / LIS

Longest Common Subsequence, Longest Increasing Subsequence. 2D DP for LCS. Patient sort for O(n log n) LIS.

Medium-Hard

String DP

Edit Distance, Palindrome Partitioning, Wildcard Matching. Compare characters, build 2D table.

Hard

Interval DP

Matrix Chain Multiplication, Burst Balloons. dp[i][j] = answer for subarray from i to j.

Hard

State Machine DP

Best Time to Buy/Sell Stock variants. States: holding, not holding, cooldown. Transitions between states.

Medium-Hard

DP on Trees/Graphs

Compute DP on tree nodes using DFS. House Robber III, Binary Tree Maximum Path Sum.

Hard

🧠 How to Identify DP Problems: 1. "Maximum/minimum of something" 2. "Count number of ways" 3. "Can we do X?" where X has overlapping subproblems 4. "Partition into subsets" 5. The problem asks for a value, not the actual path

10

Sorting Algorithms — Know How, Know When

Algorithm	Best	Average	Worst	Space	Stable?	When to Use
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	✅ Yes	Guaranteed performance, linked lists, external sort
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	❌ No	General purpose, fastest in practice (good pivot)
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	❌ No	O(1) space needed, no guaranteed O(n log n) in place
Counting Sort	O(n+k)	O(n+k)	O(n+k)	O(k)	✅ Yes	Small integer range. k is max value.
Bubble/Insertion	O(n)	O(n²)	O(n²)	O(1)	✅ Yes	Nearly sorted data, teaching only, tiny inputs

11

Binary Search — The Art of Halving

🔍 Binary Search Template (memorize this)

left = 0
right = len(arr) - 1

while left <= right:
  mid = left + (right - left) // 2  // avoids overflow
  
  if arr[mid] == target:
    return mid
  elif arr[mid] < target:
    left = mid + 1    // target is in right half
  else:
    right = mid - 1   // target is in left half

return -1  // not found

✏️ Binary Search is NOT just for sorted arrays: Any time you can say "if mid satisfies condition, I can discard half" — binary search works. Rotated arrays, finding peak elements, finding minimum in rotated sorted array — all binary search with modified conditions.

Find First/Last Position

Modified binary search. Instead of returning on found, keep searching left/right. Standard interview variation.

Medium

Search in Rotated Array

One half is always sorted. Check which half. Determine which half target is in. Recurse.

Medium — Common

Binary Search on Answer

"Minimum max" or "Maximum min" problems. Binary search on the answer space, check feasibility. FAANG favorite.

Hard

12