DSA & Problem-Solving Short Notes

Key Points

• Big-O Notation: Describes worst-case time/space growth relative to input size. Common: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).
• Two Pointers: Use two indices moving toward each other (or at different speeds) to solve sorted-array and linked-list problems in O(n) instead of O(n²).
• Sliding Window: Maintain a 'window' of elements and slide it across the array. Solves subarray/substring problems (max sum, longest substring) in O(n).
• Binary Search: Halves the search space every iteration. Requires a sorted structure or a monotonic condition. Always define left/right boundary updates carefully to avoid infinite loops.
• Hashing: Use a HashMap/Set to trade space for O(1) lookups. Classic patterns: frequency map, complement lookup (Two Sum), anagram detection.
• Stack: LIFO. Use for: balanced parentheses, next greater element, monotonic stack problems, DFS iteration.
• Queue / Deque: FIFO. Use for: BFS, sliding window maximum (deque), task scheduling.
• Linked List Tricks: Detect cycle → Floyd's (slow/fast pointers). Find middle → slow/fast pointers. Reverse in-place → prev/curr/next pointers.
• Binary Tree Traversals: Pre-order (root→L→R), In-order (L→root→R, gives BST sorted), Post-order (L→R→root). BFS uses a queue; DFS uses recursion/stack.
• BST Property: Left subtree < root < right subtree. In-order traversal yields sorted sequence. Supports O(log n) search/insert in balanced trees.
• Graph Representations: Adjacency List (sparse, memory efficient) vs Adjacency Matrix (dense, O(1) edge lookup). Most interview problems use adjacency list.
• BFS vs DFS: BFS → shortest path in unweighted graph (Level-order). DFS → cycle detection, topological sort, connected components. DFS is easier to implement recursively.
• Topological Sort: Linear ordering of vertices in a DAG such that for every edge u→v, u appears before v. Algorithms: Kahn's (BFS) or DFS post-order.
• Dynamic Programming: Break problem into overlapping subproblems. Memoisation (top-down) caches recursive results. Tabulation (bottom-up) fills a table iteratively. Identify: optimal substructure + overlapping subproblems.
• Greedy: Make the locally optimal choice at each step hoping for a global optimum. Works when greedy choice property and optimal substructure hold (e.g., Interval Scheduling, Huffman Encoding).
• Backtracking: Explore all possibilities by building a solution incrementally and abandoning ('pruning') paths that cannot lead to a valid solution. Used in: N-Queens, Subsets, Permutations.