Chapter 13: Patterns & Miscellaneous

Sort the intervals by start, then keep a merged list whose last entry is the block being grown. For each interval, compare its start with that block's end. If start <= end, the interval overlaps or touches the block, so extend the block's end to the larger of the two ends. Otherwise the interval begins after the block ends, so the block is final and the interval opens a new one. Correctness rests on the sort: every later interval starts at least as late as the current one, so if the current one cannot reach the block, nothing after it can. Sorting costs $O(n \log n)$ and the scan $O(n)$.

Four inputs break careless merges. Touching intervals such as [1, 2] and [2, 3] share the point 2, so with closed intervals the test must be start <= end, not start < end. A long interval that contains later ones, such as [1, 10] followed by [2, 3], needs end = max(end, current end); plain assignment would shrink the block to [1, 3]. Empty input must return an empty list rather than crash. And extending the caller's interval lists in place changes their data, so copy each interval first. Each fix is one line of the same scan.

The next greater element of $a_i$ is the first $a_j$ with $j > i$ and $a_j > a_i$, or -1 if none exists. Scan left to right, keeping a stack of the elements that have not yet found theirs. For each new value x, pop every stack element smaller than x and record x as its answer, then push x. Whatever remains at the end has no greater element to its right. The stack stays decreasing, since everything smaller than x was just removed. Each element is pushed once and popped at most once, so at most 2n stack operations happen in total, even though a single step may pop many elements.

Two choices define the variant. The comparison decides what is found: a decreasing stack, which pops smaller elements, finds the next greater element, while an increasing stack, which pops larger elements, finds the next smaller one. The direction decides the side: scanning right to left, or reading the stack top just before pushing, gives the previous greater or smaller element instead. Storing indices rather than values lets the answer be a distance, the current index minus the popped index. Whether equal values pop is also a choice, and it decides which duplicate wins. These variants underlie Daily Temperatures, Largest Rectangle in Histogram, and Trapping Rain Water.

The deque holds indices whose values strictly decrease from front to back. For each new index i with value x, do three steps. First, pop from the back every index whose value is at most x, since x outlives and outranks them. Second, append i. Third, if the front index is at most i - k, it has left the window, so pop it from the front. Once i reaches k - 1, the front holds the window maximum. Each index is appended once and popped at most once, so the total is $O(n)$. Store indices, not values, or expiry cannot be checked.

A max-heap reads its largest value in $O(1)$ and inserts in $O(\log n)$, but it cannot cheaply remove an arbitrary element, and the value leaving the window may sit anywhere inside it. The usual workaround is lazy deletion: push (value, index) pairs, and before reading the top, pop entries whose index has left the window. That is correct, but stale entries buried below the top are never removed, so the heap can grow to $n$ entries, each operation costs $O(\log n)$, and the total is $O(n \log n)$. The deque discards dominated values eagerly and never holds more than k indices.

Every divide-and-conquer algorithm has three steps. Divide the input into $a$ subproblems, each of size $n/b$. Conquer each one recursively, stopping at a base case small enough to solve directly. Combine the sub-answers, at a cost of $O(n^d)$. The recursion tree has $\log_b n$ levels, and level $j$ holds $a^j$ subproblems. If combining dominates, when $d > \log_b a$, the root's work wins and $T(n) = O(n^d)$. If the two balance, every level costs the same and $T(n) = O(n^d \log n)$. If subproblems multiply faster than they shrink, the leaves dominate and $T(n) = O(n^{\log_b a})$.

Maximum subarray asks for the contiguous run with the largest sum. Divide and conquer splits at the midpoint: the best run lies in the left half, in the right half, or crosses the middle. The crossing case is the best suffix of the left half plus the best prefix of the right, found in linear time, so $T(n) = 2T(n/2) + O(n) = O(n \log n)$. Kadane's algorithm is linear. Let cur be the best sum of a run ending at index i: either extend the previous run or start fresh, so cur = max(a[i], cur + a[i]). The answer is the largest cur seen. Initialize best to a[0], not 0, or an all-negative array returns 0.

The greedy-choice property says that some optimal solution begins with the greedy choice. Proving it uses an exchange argument. Take any optimal solution; if its first choice differs from the greedy one, swap in the greedy choice and show that the result is still valid and no worse. For activity selection, let g be the activity that ends first. An optimal schedule's first activity ends no earlier than g, so replacing it with g keeps every later activity compatible and leaves the count unchanged. Repeating this on the activities after g proves the schedule optimal. Without such a proof, a greedy rule is a guess.

Each nums[i] is the maximum jump length from index i; can the last index be reached? Searching jump sequences is exponential, and DP over indices is $O(n^2)$. Greedy tracks one number, reach, the farthest index reachable so far. Scan left to right. If i > reach, index i is unreachable, and so is everything beyond it, so return False. Otherwise set reach = max(reach, i + nums[i]), and return True once reach covers the last index. This is safe because every index up to reach is reachable, so the best jump from any of them is available. Jump Game II reuses the scan.

Each object becomes events at the coordinates where it starts and stops mattering: an interval [s, e] yields (s, +1) and (e, -1). Sort all events by coordinate, then walk through them while maintaining a running state, here the number of active intervals. Between consecutive events the state is constant, so checking it only at events is exact, and the largest running count is the maximum overlap. Ties matter: at equal coordinates, the order of ends and starts decides whether touching intervals count as overlapping. For richer questions the state becomes a set or balanced tree of active objects, as in segment intersection.

Meeting Rooms II asks for the fewest rooms that can host every meeting. Meetings are half-open, [start, end), so a room freed at time t can host a meeting starting at t. The answer equals the largest number of meetings in progress at once. Sweep the events with one rule for ties: at equal times, process -1 before +1. Sorting (time, delta) tuples does this automatically, because -1 sorts before +1. An equivalent method sorts the starts and the ends separately and walks both lists with two pointers. A third keeps a min-heap of end times and reuses the room that frees earliest, which also assigns each meeting a room.