Core Concepts

• 1Binary heap structure and operations: a binary min-heap is a complete binary tree where every parent is smaller than its children. Stored as an array: parent of index i is at (i-1)//2; children are at 2i+1 and 2i+2. PUSH: append to end, then 'sift up' — repeatedly swap with parent while parent > current. O(log n). POP min: replace root with last element, remove last, then 'sift down' — repeatedly swap with the smaller child while any child < current. O(log n). PEEK min: O(1) (just return arr[0]). BUILD HEAP from an array: apply sift-down to all non-leaf nodes from right to left. O(n) — not O(n log n). This is the Floyd algorithm used in heapsort. Python's heapq module implements a min-heap.
• 2Max-heap in Python — the negation trick: Python's heapq only provides a min-heap. To simulate a max-heap, negate the values: push -x instead of x; the 'minimum' of negated values is the maximum of original values. When popping, negate again to get the original value. Example: to get the maximum: heapq.heappush(heap, -x); max_val = -heapq.heappop(heap). For (priority, value) tuples: heapq.heappush(heap, (-priority, value)). This trick is used in virtually every heap problem in Python and is the first thing to mention in any interview involving max-heaps.
• 3Top-K elements — heap vs sorting: to find the K largest elements from n elements, you have two approaches: (1) Sort all n elements in O(n log n), take the last K. (2) Maintain a min-heap of size K: for each element, push it onto the heap; if heap size exceeds K, pop the minimum. Result is the K largest elements in O(n log K) time and O(K) space. For K << n, the heap approach is significantly faster. The heap approach also works for streaming data where you don't have all elements upfront. LC 215 (Kth Largest) uses QuickSelect for O(n) average, but the heap approach is simpler and more reliable in interviews.
• 4Merge K sorted lists — heap as a priority queue: given K sorted lists, merge them into one sorted list. Naive: merge two at a time — O(nK) total. Heap approach: push the first element of each list into a min-heap as (value, list_index, element_index). While heap is non-empty: pop minimum (val, i, j); add val to result; if list i has more elements, push (list_i[j+1], i, j+1). Total O(n log K) where n is total elements. This is the exact algorithm used in external sorting (merging K sorted files). The heap always contains exactly K elements (one per list) — O(K) space.
• 5Two-heap pattern for median of a data stream: maintain two heaps: a MAX-heap for the lower half and a MIN-heap for the upper half. Invariant: max_heap contains the smaller half; min_heap contains the larger half; sizes differ by at most 1. To add a number: push to max_heap first (use negation); if max_heap top > min_heap top (order violated), move max_heap top to min_heap; rebalance so sizes differ by at most 1. To get median: if sizes are equal, average of both tops; otherwise return the top of the larger heap. Each addNum is O(log n); getMedian is O(1). The two-heap pattern generalizes: LC 480 (sliding window median) uses a similar approach with lazy deletion.
• 6Greedy algorithm correctness — the exchange argument: a greedy algorithm is correct if for ANY non-greedy solution, you can swap one element toward the greedy choice without making things worse, and repeat until you reach the greedy solution. Example: ACTIVITY SELECTION — sort by finish time, greedily pick the earliest-finishing activity that doesn't conflict. Proof: suppose the optimal solution picks activity B first but the greedy picks A (A finishes earlier). Replace B with A in the optimal solution — A finishes no later than B, so A doesn't conflict with anything B didn't conflict with. The modified solution is no worse. This exchange argument proves greedy is at least as good as any optimal solution.
• 7Classic greedy problems and their key insights: JUMP GAME (LC 45) — greedily track the farthest reachable index; at each step, update farthest = max(farthest, i + nums[i]). INTERVAL SCHEDULING (LC 435) — sort by END time, greedily pick intervals; if start of current >= end of last picked, take it (this minimizes the number of overlapping intervals removed). GAS STATION (LC 134) — if total gas >= total cost, a solution exists; start from the first index where the running total dips below 0 (reset start). CANDY (LC 135) — two passes: left-to-right (each child with higher rating than left gets one more), right-to-left (each child with higher rating than right gets max of current and right+1).
• 8Monotonic stack — next greater element: a monotonic stack is a stack that maintains elements in monotonically increasing or decreasing order. For NEXT GREATER ELEMENT: iterate left to right, maintain a decreasing stack. For each element x: while stack is non-empty and stack top < x, the top's next greater element is x — pop it and record the answer. Push x. Elements that are never popped (remain in stack when iteration ends) have no next greater element. O(n) time — each element is pushed and popped at most once. The stack contains indices (not values) in practice, to record which original position each answer belongs to.
• 9Largest rectangle in histogram — monotonic stack: LC 84. For each bar, we want to find the largest rectangle that uses this bar as the shortest bar. The key insight: a rectangle extending through position i with height h[i] extends left until it hits a shorter bar and right until it hits a shorter bar. Use a monotonic increasing stack (by height). When you pop a bar (because current bar is shorter), the current bar is the right boundary and the new stack top is the left boundary. Width = right - left - 1. Area = height times width. O(n) time. LC 85 (maximal rectangle in 0-1 matrix) reduces to running this algorithm on each row's 'histogram' — O(nm) total.

Key Patterns & Templates