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