Capstone: Complete DSA Revision

MODULE 01: Arrays & Strings
 — Arrays, Two Pointers, Sliding Window, Prefix Sum, Array Problems

MODULE 02: Linked Lists
 — LL Basics, Operations, Problems

MODULE 03: Stacks & Queues
 — Stack Basics, Queue Basics, Valid Parentheses, Next Greater Element

MODULE 04: Sorting Algorithms
 — Bubble, Selection, Insertion, Merge, Quick Sort

MODULE 05: Recursion & Backtracking
 — Recursion Basics, Patterns, Backtracking, N-Queens

MODULE 06: Trees
 — Tree Basics, Height, Construction, Path, BST

MODULE 07: Heaps & Priority Queues
 — Heap operations, Top K elements, Median stream

MODULE 08: Graphs
 — Graph Basics, BFS/DFS, Dijkstra, MST, Cycle Detection, Topological Sort

MODULE 09: Binary Search
 — BS Basics, Lower/Upper Bound, Rotated Array, BS on Answer, Problems

MODULE 10: Tries & Advanced
 — Trie, Segment Tree, Bit Manipulation, Interview Patterns, Capstone

+-----------------------------------------------------+
? Operation — Time — Space ?
?---------------------------+----------+--------------?
? Array Access — O(1) — O(1) ?
? Array Search (unsorted) — O(n) — O(1) ?
? Array Search (sorted) — O(logn) — O(1) ?
? Array Insert/Delete (end) — O(1) — O(1) ?
? Array Insert/Delete (mid) — O(n) — O(n) ?
?---------------------------+----------+--------------?
? Linked List Access — O(n) — O(1) ?
? Linked List Insert (head) — O(1) — O(1) ?
? Linked List Search — O(n) — O(1) ?
?---------------------------+----------+--------------?
? Stack Push/Pop — O(1) — O(n) ?
? Queue Enqueue/Dequeue — O(1) — O(n) ?
?---------------------------+----------+--------------?
? Merge Sort — O(nlogn)? O(n) ?
? Quick Sort (avg) — O(nlogn)? O(logn) ?
? Quick Sort (worst) — O(n?) — O(n) ?
?---------------------------+----------+--------------?
? BST Search/Insert — O(h) — O(h) ?
? BST (balanced) — O(logn) — O(logn) ?
?---------------------------+----------+--------------?
? Heap Insert/Extract — O(logn) — O(n) ?
? Heap Find Min/Max — O(1) — O(1) ?
?---------------------------+----------+--------------?
? BFS/DFS (adj list) — O(V+E) — O(V) ?
? Dijkstra — O(ElogV)? O(V) ?
?---------------------------+----------+--------------?
? Binary Search — O(logn) — O(1) ?
? Trie Insert/Search — O(L) — O(ALPHABET?L?N)?
? Segment Tree Build — O(n) — O(4n) ?
? Segment Tree Query/Update — O(logn) — O(1) ?
+-----------------------------------------------------+

# Binary Search Template
def bs(arr, target):
 lo, hi = 0, len(arr) - 1
 while lo <= hi:
 mid = (lo + hi) // 2
 if arr[mid] == target: return mid
 elif arr[mid] < target: lo = mid + 1
 else: hi = mid - 1
 return -1

# BFS Template
from collections import deque
def bfs(graph, start):
 q = deque([start])
 visited = {start}
 while q:
 node = q.popleft()
 for nb in graph[node]:
 if nb not in visited:
 visited.add(nb)
 q.append(nb)

# Union-Find Template
class UF:
 def __init__(self, n):
 self.p = list(range(n))
 def find(self, x):
 if self.p[x] != x: self.p[x] = self.find(self.p[x])
 return self.p[x]
 def union(self, a, b):
 pa, pb = self.find(a), self.find(b)
 if pa != pb: self.p[pa] = pb; return True
 return False

# Trie Template
class TrieNode:
 def __init__(self):
 self.ch = {}; self.end = False