Chapter 13: Patterns & Miscellaneous
Master essential algorithmic patterns that appear across countless interview problems: interval manipulation, monotonic stacks, sliding window optimizations, divide and conquer strategies, greedy reasoning, and line sweep techniques. These patterns are the connective tissue between data structures and problem-solving mastery.
Chapter Overview
This final chapter covers algorithmic patterns that do not fit neatly into a single data structure category but appear with remarkable frequency in interviews and real-world systems. Each pattern represents a reusable problem-solving template.
Interval problems teach you to reason about overlapping ranges---scheduling meetings, merging time slots, or detecting conflicts. Monotonic stacks unlock efficient solutions to "next greater element" problems that would otherwise require nested loops. Sliding window maximum combines deques with the sliding window pattern for O(n) range-max queries.
Divide and conquer shows how breaking a problem into independent subproblems (and combining their solutions) leads to elegant algorithms like merge sort and Karatsuba multiplication. Greedy algorithms demonstrate when making the locally optimal choice at each step provably yields the globally optimal result. Line sweep transforms 2D geometric or scheduling problems into sorted event processing.
Mastering these patterns is about recognizing which template applies to a new problem. Once you identify the pattern, the implementation follows naturally from the template.
Chapter Roadmap
Click any topic to jump in
Interval Problems
Representation, overlap detection, and linear-time insertion into sorted intervals.
Merge Intervals
$O(n \log n)$ sort-and-sweep with careful edge-case handling.
Each tackles a different aspect
Monotonic Stack
Amortized $O(n)$ next/previous greater/smaller via stack invariants.
Sliding Window Maximum
Monotonic deque gives $O(n)$ — beating heap-based $O(n \log k)$.
Each tackles a different aspect
Divide and Conquer
Master Theorem template and Kadane as the linear alternative to $O(n \log n)$.
Greedy Algorithms
Greedy-choice property, exchange arguments, and the Jump Game reach invariant.
Line Sweep
Event-based processing for maximum-overlap and meeting-rooms problems.
Interval problems deal with ranges represented as [start, end] pairs. The fundamental operations are detecting overlaps, inserting new intervals into a sorted list, and determining how intervals relate to each other (disjoint, overlapping, contained).
Two intervals [a, b] and [c, d] overlap if and only if a <= d and c <= b. This simple condition is the foundation of nearly every interval algorithm. Sorting intervals by their start (or end) point transforms chaotic overlap detection into a clean linear scan.
In this topic
Interval Representation and Overlap Detection
An interval [start, end] represents a continuous range. Two intervals overlap when neither one ends before the other begins. The non-overlap condition is a_end < b_start or b_end < a_start. Negating this gives the overlap condition: a_start <= b_end and b_start <= a_end. Sorting intervals by start time ensures that for consecutive intervals in the sorted order, you only need to check if the current interval's start is less than or equal to the previous interval's end.
Two intervals and overlap iff (the standard two-inequality test). Detecting overlap is ; detecting pairwise overlaps in a set is naively but after sorting by start (sweep-line). The convention on closed vs. half-open endpoints changes which inequalities are strict — be consistent.
Do intervals [1, 5] and [3, 8] overlap? What about [1, 5] and [6, 9]?
Insert Interval
Given a sorted list of non-overlapping intervals and a new interval, insert the new interval and merge any resulting overlaps. The approach splits the existing intervals into three groups: those entirely before the new interval (end < new_start), those that overlap with the new interval (merged together), and those entirely after (start > new_end). This runs in O(n) time with a single pass.
Given a sorted list of non-overlapping intervals and a new interval , insert in : copy intervals ending before , merge all intervals overlapping by taking of starts and of ends, then copy remaining intervals. Linear time is optimal since the output may differ in up to positions.
Insert [4, 8] into [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]].