Patterns

Recognizing `O(n)` or `O(n^2)` on a slide is one thing; staring at unfamiliar code in an interview and confidently announcing its complexity is another. The gap between those two skills is filled by analysis technique, and that technique is what this lesson hands you. **Time Complexity Analysis Techniques** turns Big-O classification into a repeatable workflow you can apply to any snippet. You will analyze single loops with non-standard step sizes, nested loops where the inner bounds depend on the outer variable, sequential blocks that you sum and simplify, `if`/`else` branches where you take the worst case, and the telltale halving-or-multiplying patterns that produce `O(log n)`. Along the way you will see why a triangular loop summing `0 + 1 + 2 + ... + (n-1)` lands at `O(n^2)`, and why constant-bounded loops collapse to `O(1)` no matter how many times they run. In **Big-O Notation (Upper Bound)**, you learned what `O(f(n))` means and how to spot the dominant term in a polynomial. This lesson sharpens that recognition into a procedure: count iterations precisely, multiply for nesting, add for sequencing, and drop everything but the dominant term. Once you can dissect time complexity from real code, you will be ready for **Space Complexity Fundamentals**, where you apply the same Big-O lens to memory usage instead of operation counts.

Standard binary search returns an arbitrary index of a target if duplicates exist, but real problems usually want the _first_ such index, the _last_ such index, or the smallest capacity that ships every package within `D` days. Each variation needs a slightly different loop condition and return value, and getting one wrong produces an off-by-one bug or an infinite loop. **Binary Search Templates** turns those variations into a small set of memorable templates. You will work through first and last occurrence with `<=` versus `<` loop conditions, lower bound and upper bound (the templates behind Python's `bisect_left` and `bisect_right`), binary search on the answer space (the "minimize the maximum" pattern that solves Koko Eating Bananas, Capacity to Ship Packages, and Split Array Largest Sum), and search in rotated sorted arrays where the invariant holds for exactly one half at each step. In **Binary Search (Intro)**, you wrote the canonical exact-match loop and learned why it is `O(log n)`. This lesson keeps the halving idea but switches the question from "is `target` here?" to "what is the smallest index that satisfies a monotonic predicate?". Next, **Linked List Algorithms** turns to pointer manipulation patterns.

Two Sum was a hard problem in 2010. With a hash map it becomes a six-line interview warm-up: walk the array once, and for each value `x` ask whether `target - x` is already in the map. The same shape, single-pass plus complement lookup, solves "first duplicate," "contains nearby duplicate," "longest substring without repeats," and an entire family of trade-space-for-time problems. **Hashing Techniques** catalogs those patterns. You will work through frequency counting (most/least frequent element, group anagrams via sorted-key trick), the two-sum complement template and its three-sum / four-sum extensions, existence checking and duplicate detection, index mapping where you store positions alongside values, and a first conceptual look at rolling hashes that prepare you for Rabin-Karp later. The lesson also discusses when a hash map is overkill versus when it is the obviously correct tool. In **Hash Map (Dictionary) Basics**, you saw how hashing achieves expected `O(1)` insertion and lookup. This lesson is where that constant-time primitive turns into algorithmic leverage: brute-force `O(n^2)` scans collapse into a single pass that uses the map as an oracle. From here you move into the paid track with **Sorting (Advanced)**, which trades hash-map lookups for divide-and-conquer to break the `O(n^2)` sorting barrier.

Reversing a singly linked list is a four-line iteration with three pointers (`prev`, `curr`, `next`), and yet roughly a third of candidates implement it incorrectly under interview pressure. The reason is that linked-list problems give you no random access: every operation has to be expressed as careful, ordered pointer rewrites, and one missed assignment loses the rest of the list forever. **Linked List Algorithms** is the lesson where pointer manipulation becomes a reliable skill. You will reverse a list iteratively and recursively, then extend the technique to reverse in groups of `k`. You will use Floyd's fast and slow pointers to detect cycles, find the cycle start, locate the middle element, and check whether a list is a palindrome. You will merge two sorted lists, then merge `k` sorted lists with a min-heap. The lesson also covers removing the nth node from the end, finding the intersection of two lists, deep-copying a list with random pointers, and the dummy-node trick that eliminates head-edge cases entirely. In **Linked Lists (Singly)**, you saw how nodes and `next` pointers form a list and why insertion at a known position is `O(1)`. **Two Pointers (Intro)** introduced fast and slow indices on arrays; this lesson reuses the same idea on pointer-linked nodes. Next, **Tree Algorithms** generalizes pointer-and-recursion thinking to branching structures.

Boyer-Moore is the algorithm `grep` actually uses, and it has a counterintuitive property: longer patterns make it _faster_, not slower, because the bad-character rule lets it skip whole chunks of the text without inspecting them. The best case is `O(n / m)`, sublinear in the text length. The same insight (start from the right, jump aggressively on mismatch) defines a different family of pattern-matching algorithms from the linear-scan family of KMP and Z. **Pattern Matching Algorithms** rounds out the string-search toolkit. You will implement Boyer-Moore with both the bad-character rule and the good-suffix rule, build a deterministic finite automaton (DFA) from a pattern and use the resulting state-transition table for `O(n)` matching after `O(m * |alphabet|)` preprocessing, and extend pattern search into two dimensions row by row. The lesson closes with a head-to-head comparison of every string-matching algorithm you have seen so far (KMP, Z, Rabin-Karp, Manacher, Aho-Corasick, Boyer-Moore, DFA), so you can pick the right tool for any matching task: long patterns, multi-pattern, streaming, or 2D. In **String Algorithms**, you mastered the failure-function family of linear-time matchers. This lesson adds the right-to-left family and the automaton-construction family. From here, **Advanced Greedy & Data Structures** turns to monotonic stacks.

Imagine an array of a million numbers and a thousand questions of the form "what is the sum of elements between index `l` and `r`?". The naive answer loops through each query, doing roughly a billion additions in total. Prefix sums turn the same workload into a million additions plus a thousand subtractions, with answers in constant time per query. **Prefix Sum & Difference Array** covers the technique in three layers. You will build 1D prefix sums where `prefix[i] = prefix[i-1] + arr[i]` and answer any range sum in `O(1)`. You will then learn the inverse, the difference array, which turns repeated `O(n)` range updates into `O(1)` updates that you reconstruct in a single final pass. The lesson finishes with 2D prefix sums and the inclusion-exclusion trick for answering submatrix sum queries, plus quick variants like prefix XOR and prefix product. In **Arrays & Strings**, you saw why arrays support `O(1)` random access; that property is exactly what makes prefix lookup possible. **Iteration Patterns on Arrays/Strings** trained you to think in terms of single passes, and the prefix sum is the first pattern where one preprocessing pass replaces an entire family of later loops. From here you will move into **Sorting (Elementary)**, where rearranging the array unlocks an entirely different class of techniques.

Given a sorted array and a target sum, the brute-force "check every pair" approach is `O(n^2)`. With two indices walking inward from opposite ends, the same problem drops to `O(n)`: if the current pair sums too low, move the left pointer right; if it sums too high, move the right pointer left. **Two Pointers (Intro)** turns that insight into a reusable pattern with two main shapes. The opposite-direction variant has pointers converge from both ends and powers problems like pair sum, palindrome check, reverse in place, and container with most water. The same-direction (fast and slow) variant has both pointers walk forward at different speeds and powers in-place filtering problems like remove duplicates from a sorted array, move zeros to the end, and the linked-list cycle detection you will revisit later. In **Arrays & Strings**, you learned how a single index walks across an array. This lesson coordinates two indices in a way that exploits sorted order or a structural invariant to skip work an inner loop would otherwise repeat. Next, **Sliding Window (Intro)** generalizes the same-direction pointer pair into an expanding and shrinking range that solves contiguous-subarray problems.