Top 'K' Elements

Problem: Return the k-th largest value in an unsorted array (counting duplicates: in [3,3,2] the 2nd largest is 3).

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ k ≤ nums.length ≤ 10⁵ · -10⁴ ≤ nums[i] ≤ 10⁴

From brute force to the pattern: Sorting is O(n log n). A size-k min-heap is O(n log k); quickselect averages O(n) but is O(n²) in the worst case.

Spot it: "k-th largest", unsorted, no need for the full order → size-k min-heap.

Key insight: After every element has been offered, a min-heap of the k biggest values has the k-th biggest at its root. Once the heap is full, a newcomer only gets in if it beats the root, and then the root is thrown out to make room.

Approach:

1. While the heap has fewer than k numbers, just push each number in.
2. Once it's full, for each further number: if number > heap[0], it beats the weakest of the current top k, so pop the root and push number.
3. Otherwise ignore number. It can't be in the top k.
4. At the end, the heap holds the k largest values and heap[0] is the k-th largest.

import heapq
from typing import List

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # heapq.heappush(heap, x) adds x; heapq.heappop(heap) removes the
        # smallest; heap[0] is always the smallest. That's a MIN-heap.
        heap = []
        for i in range(len(nums)):
            number = nums[i]
            if len(heap) < k:
                # The club still has empty seats: let the number in.
                heapq.heappush(heap, number)
            elif number > heap[0]:
                # The newcomer beats the weakest VIP (heap[0]).
                # Throw the weakest out, then seat the newcomer.
                heapq.heappop(heap)
                heapq.heappush(heap, number)
            # Otherwise the number is too small for the top k: ignore it.
        # The heap holds the k largest numbers.
        # The smallest of them (heap[0]) is the k-th largest overall.
        return heap[0]

What the code is doing, line by line:

1. heap = []. An empty min-heap: heapq keeps the smallest number at heap[0] after every push or pop.
2. for i in range(len(nums)) / number = nums[i]. Look at each number once, left to right.
3. if len(heap) < k. Fewer than k numbers kept so far, so every number is (for now) one of the top k: heappush it.
4. elif number > heap[0]. The heap is full. heap[0] is the weakest of the current top k. If the new number is bigger, the weakest is no longer in the top k: heappop removes it and heappush seats the newcomer. The heap stays at exactly k numbers.
5. Otherwise do nothing. A number that doesn't beat the weakest of k bigger numbers can't be in the top k.
6. return heap[0]. The heap now holds the k largest numbers, and its smallest member is the k-th largest.

Dry run on the example: nums = [3, 2, 1, 5, 6, 4], k = 2. Heap contents are listed in sorted order.

The heap holds the two largest numbers, 5 and 6, so the answer is heap[0] = 5.

Edge cases to test:

• k = 1 → the maximum.
• k = n → the minimum.
• Duplicates count separately, e.g. [3, 3, 3], k = 2 → 3.

Complexity: O(n log k) time, O(k) space. (Quickselect averages O(n) but is O(n²) in the worst case.)

Problem: Return the k values that appear most often in nums (any order).

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · -10⁴ ≤ nums[i] ≤ 10⁴ · k is in the range [1, the number of unique elements in the array]. · It is guaranteed that the answer is unique.

From brute force to the pattern: Sorting all distinct values by frequency is O(u log u). A size-k heap is O(u log k), and bucket sort (index = frequency) is O(n).

Spot it: "k most frequent" → count first, then Top K by the frequency score.

Key insight: Count with a plain dictionary, then run the size-k min-heap on (frequency, value) tuples. The least frequent of the current top k sits at the root and is evicted first.

Approach:

1. Count every value in a dictionary (value → frequency).
2. Push each (freq, value) pair into a min-heap.
3. Whenever the heap holds more than k pairs, pop the least frequent.
4. The values left in the heap are the k most frequent.

import heapq
from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Step 1: count how many times each value appears.
        counts = {}
        for i in range(len(nums)):
            value = nums[i]
            if value not in counts:
                counts[value] = 0
            counts[value] = counts[value] + 1

        # Step 2: keep a min-heap of (frequency, value) pairs, at most k of them.
        # heappush adds a pair; heappop removes the pair with the SMALLEST
        # frequency (tuples are compared by their first field first).
        heap = []
        for value in counts:
            frequency = counts[value]
            heapq.heappush(heap, (frequency, value))
            if len(heap) > k:
                heapq.heappop(heap)          # drop the least frequent value

        # Step 3: the values still in the heap are the k most frequent.
        result = []
        for i in range(len(heap)):
            pair = heap[i]
            result.append(pair[1])           # field 1 of the pair is the value
        return result

What the code is doing, line by line:

1. Count. Walk through nums. The first time a value is seen, counts[value] = 0; then every sighting adds 1. Afterwards counts maps each value to how often it appears.
2. heap = []. A min-heap of (frequency, value) pairs. Because frequency comes first, heap[0] is always the least frequent pair being kept.
3. Push each pair. for value in counts visits each distinct value once. Push (frequency, value).
4. Pop when over k. If the heap now holds k + 1 pairs, heappop removes the least frequent one: it can't be in the top k because k values beat it.
5. Collect the answer. Walk over the pairs left in the heap and append field [1] (the value). Any order is accepted.

Dry run on the example: nums = [1,1,1,2,2,3], k = 2. After counting: counts = {1: 3, 2: 2, 3: 1}.

Reading field [1] from each remaining pair gives [2, 1], i.e. the values 1 and 2 (any order is accepted).

Edge cases to test:

• k equals the number of distinct values → all of them.
• A single element.
• Negative values.

Complexity: O(n + m log k) where m = distinct values; O(m) space. Follow-up: bucket sort by frequency gives O(n) (see the Python file).

Problem: Given points [x, y], return the k closest to (0, 0).

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ k ≤ points.length ≤ 10⁴ · -10⁴ ≤ xi, yi ≤ 10⁴

From brute force to the pattern: Sorting every point by distance is O(n log n). A size-k heap keeps just the best k: O(n log k).

Spot it: "k closest" = k smallest distances → size-k max-heap (negate the key).

Key insight: Compare squared distances x² + y²; the square root never changes the order. The root of the max-heap is the farthest of the current k, so it's evicted when a closer point appears.

Approach:

1. Score each point by its squared distance x² + y². No square root is needed to compare.
2. Push (-dist, x, y). The negation turns Python's min-heap into a max-heap.
3. If the heap has more than k points, pop. That removes the farthest one.
4. Return the points left in the heap.

import heapq
from typing import List

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        # heapq is a MIN-heap (heappop removes the smallest). We want to throw
        # away the FARTHEST point, so we push the NEGATIVE distance: the
        # farthest point gets the most negative key and sits at heap[0].
        heap = []
        for i in range(len(points)):
            point = points[i]
            x_coord = point[0]
            y_coord = point[1]
            # Squared distance. No square root needed: it doesn't change the order.
            distance = x_coord * x_coord + y_coord * y_coord
            heapq.heappush(heap, (-distance, x_coord, y_coord))
            if len(heap) > k:
                heapq.heappop(heap)          # removes the FARTHEST point kept so far
        # Turn the surviving tuples back into [x, y] lists.
        result = []
        for i in range(len(heap)):
            entry = heap[i]
            result.append([entry[1], entry[2]])
        return result

What the code is doing, line by line:

1. heap = []. This will be a max-heap by distance, built from Python's min-heap by negating the distance.
2. Read one point. point = points[i], then x_coord = point[0] and y_coord = point[1], one value per line.
3. distance = x² + y². The real distance is the square root of this, but a bigger squared distance always means a bigger real distance, so we can compare squares and skip the slow square root.
4. Push (-distance, x_coord, y_coord). The farthest point has the most negative first field, so it becomes heap[0].
5. If more than k points are kept, heappop removes heap[0]: the farthest of the k+1. It can't be one of the k closest.
6. Build the answer. Walk over the surviving tuples and append [entry[1], entry[2]] (the coordinates) to result. Any order is accepted.

Dry run on the example: points = [[3,3], [5,-1], [-2,4]], k = 2.

The survivors give the answer [[-2, 4], [3, 3]] (any order is accepted). For LeetCode's first example, [[1,3],[-2,2]] with k = 1: distances 10 and 8, so [1,3] is popped and the answer is [[-2,2]].

Edge cases to test:

• k = n → every point.
• Ties in distance (any of them may be returned).
• Points with negative coordinates.

Complexity: O(n log k) time, O(k) space.

Problem: Merge k sorted linked lists into one sorted list.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: k == lists.length · 0 ≤ k ≤ 10⁴ · 0 ≤ lists[i].length ≤ 500 · -10⁴ ≤ lists[i][j] ≤ 10⁴ · lists[i] is sorted in ascending order. · The sum of lists[i].length will not exceed 10⁴.

From brute force to the pattern: Collecting all values and sorting is O(N log N); merging the lists one by one is O(k · N). A heap of the k heads always yields the next smallest in O(log k): O(N log k) total.

Spot it: At every step you need "the smallest head among k lists". Repeatedly taking the minimum of a changing set is a heap's job.

Key insight: Put each list's head in a min-heap. Pop the smallest, attach it to the result, and push that node's next. The heap never holds more than k nodes. Add the list index i as a tie-breaker because ListNode objects can't be compared.

Approach:

1. Push (head.val, i, head) for every non-empty list. The index i breaks ties, so nodes are never compared.
2. Pop the smallest node and attach it to the tail of the result.
3. If that node has a next, push it. It now represents its list in the race.
4. Repeat until the heap is empty, then return dummy.next.

import heapq
from typing import List, Optional

# Definition for singly-linked list (LeetCode provides this class).
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # The heap holds one (value, list_index, node) tuple per list: that
        # list's current front node. heappop always returns the tuple with the
        # smallest value. list_index breaks ties, so Python never tries to
        # compare two ListNode objects (which would crash).
        heap = []
        for i in range(len(lists)):
            head = lists[i]
            if head is not None:             # skip empty lists
                heapq.heappush(heap, (head.val, i, head))

        # dummy is a fake first node; tail is the last node of the merged list.
        dummy = ListNode()
        tail = dummy
        while len(heap) > 0:
            # Take the smallest front node out of all the lists.
            entry = heapq.heappop(heap)
            list_index = entry[1]
            node = entry[2]
            # Hook it onto the end of the merged list.
            tail.next = node
            tail = node
            # That node's successor is now the front of its list: add it.
            if node.next is not None:
                heapq.heappush(heap, (node.next.val, list_index, node.next))
        # Skip the fake first node.
        return dummy.next

What the code is doing, line by line:

1. class ListNode is LeetCode's linked-list node: a value and a pointer to the next node. It's shown so the code runs on its own.
2. Seed the heap. For each list i that isn't empty, push (head.val, i, head). heappush keeps the smallest tuple at heap[0]. If two values tie, Python compares the second field, i, which is always different, so it never reaches the third field (a ListNode can't be compared and would raise TypeError).
3. dummy = ListNode(), tail = dummy. A placeholder node in front of the answer, so attaching the very first real node needs no special case. tail always points at the last node attached so far.
4. while len(heap) > 0. As long as some list still has nodes left.
5. entry = heapq.heappop(heap). Remove the tuple with the smallest value. Read entry[1] (which list it came from) and entry[2] (the node).
6. tail.next = node, tail = node. Attach the node to the end of the merged list and move tail forward.
7. Push the successor. If the node has a next, that node is now the front of the same list, so it joins the heap with the same list_index. The heap never holds more than one node per list.
8. return dummy.next. The first real node of the merged list.

Dry run on the example: lists = [[1,4,5], [1,3,4], [2,6]]. Heap entries are shown as (value, list_index), in sorted order. Start: heap = (1,0), (1,1), (2,2).

The heap is empty, so the merged list is 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6. Notice loop 4→5: the two 4s tie on value, and the list index (0 before 1) decides.

Edge cases to test:

• An empty array of lists, or lists that are all empty.
• One list only.
• Equal values across lists (the heap needs a tie-breaker so it never compares nodes).

Complexity: O(N log k) for N total nodes, O(k) heap space.

Problem: Design a structure with addNum(num) and findMedian() over all numbers added so far.

Solve it on LeetCode ↗

Constraints: -10⁵ ≤ num ≤ 10⁵ · There will be at least one element in the data structure before calling findMedian. · At most 5 * 10⁴ calls will be made to addNum and findMedian.

From brute force to the pattern: Sorting on every findMedian call is O(n log n) each; keeping a sorted list makes inserts O(n). Two balanced heaps make addNum O(log n) and findMedian O(1).

Spot it: "median" of a "stream". The median is the boundary between the smaller half and the larger half, so keep two heaps: a max-heap for the lower half and a min-heap for the upper half.

Key insight: Keep two rules. (1) Every value in lo ≤ every value in hi. (2) len(lo) equals len(hi) or is one more. Then the median is lo's top, or the average of both tops. To insert, push into lo, move lo's max over to hi (this fixes rule 1), then move one back if hi got bigger (this fixes rule 2).

Approach:

1. Keep lo (a max-heap, stored negated) for the smaller half and hi (a min-heap) for the larger half.
2. addNum: push into lo, then move lo's maximum into hi. Now every value in lo ≤ every value in hi.
3. If hi has more items than lo, move hi's minimum back to lo, so len(lo) is len(hi) or one more.
4. findMedian: odd count → lo's top; even count → average of both tops.

import heapq

class MedianFinder:
    def __init__(self):
        # lo holds the SMALLER half as a MAX-heap. heapq is a min-heap, so we
        # store NEGATIVE numbers: the biggest real number is the most negative
        # and sits at lo[0].
        self.lo = []
        # hi holds the LARGER half as a normal MIN-heap: hi[0] is its smallest.
        self.hi = []

    def addNum(self, num: int) -> None:
        # 1) Put the new number into lo (negated, because lo is a max-heap).
        heapq.heappush(self.lo, -num)
        # 2) Move lo's biggest number over to hi. This guarantees every
        #    number in lo is <= every number in hi.
        biggest_of_lo = -heapq.heappop(self.lo)
        heapq.heappush(self.hi, biggest_of_lo)
        # 3) Keep the sizes balanced: lo may have one extra, hi may not.
        if len(self.hi) > len(self.lo):
            smallest_of_hi = heapq.heappop(self.hi)
            heapq.heappush(self.lo, -smallest_of_hi)

    def findMedian(self) -> float:
        # Odd count: lo has the extra number, and its top is the middle one.
        if len(self.lo) > len(self.hi):
            return float(-self.lo[0])
        # Even count: average the two middle numbers (the two tops).
        top_of_lo = -self.lo[0]
        top_of_hi = self.hi[0]
        return (top_of_lo + top_of_hi) / 2

What the code is doing, line by line:

1. __init__ creates two empty lists. self.lo is the smaller half stored as negatives (so -self.lo[0] is its biggest real value). self.hi is the larger half as a normal min-heap (so self.hi[0] is its smallest).
2. heapq.heappush(self.lo, -num). Every new number first goes into lo, negated.
3. Move lo's biggest to hi. heappop(self.lo) returns the most negative stored value; negating it gives the biggest real number in lo, which we push into hi. If the new number belonged in the upper half, this is where it ends up; either way, everything in lo is now ≤ everything in hi.
4. Rebalance. Step 2 always makes hi one bigger. If hi now has more numbers than lo, pop hi's smallest and push it (negated) into lo. Afterwards len(lo) equals len(hi) or is one more.
5. findMedian, odd count. lo holds the extra number, so its top (-self.lo[0]) is the exact middle. float(...) makes the return type a float as LeetCode expects.
6. findMedian, even count. The two middle numbers are the top of lo and the top of hi; return their average.

Dry run on the example: addNum(1), addNum(2), findMedian(), addNum(3), findMedian(). lo is shown both as stored (negatives) and as real values.

Inside addNum(3): 3 goes into lo, is immediately moved to hi (now [2, 3]), and then hi is bigger than lo, so its smallest, 2, moves back to lo.

Edge cases to test:

• One number → it is the median.
• Even count → the average of the two middle numbers.
• Duplicates and negative numbers.

Complexity: addNum O(log n), findMedian O(1), O(n) space.

Problem: Design a class that's given k and some starting numbers. Each call add(val) inserts a number and returns the current k-th largest.

Solve it on LeetCode ↗

Constraints: 0 ≤ nums.length ≤ 10⁴ · 1 ≤ k ≤ nums.length + 1 · -10⁴ ≤ nums[i] ≤ 10⁴ · -10⁴ ≤ val ≤ 10⁴ · At most 10⁴ calls will be made to add.

From brute force to the pattern: Sorting after each add is O(n log n) per call. A size-k min-heap makes each add O(log k).

Spot it: A stream plus "k-th largest" is the size-k min-heap in its purest form.

Approach:

1. Push the starting numbers one by one, popping whenever the heap holds more than k.
2. add: push val, and pop if the size exceeds k.
3. Return heap[0], the weakest of the top k, which is the k-th largest.

import heapq
from typing import List

class KthLargest:
    def __init__(self, k: int, nums: List[int]):
        self.k = k
        # A MIN-heap that will hold the k largest numbers seen so far.
        # heappush adds a number; heappop removes the smallest one.
        self.heap = []
        for i in range(len(nums)):
            heapq.heappush(self.heap, nums[i])
            if len(self.heap) > k:
                heapq.heappop(self.heap)       # too many: drop the smallest

    def add(self, val: int) -> int:
        # Same two moves for every new number: push it, pop if too many.
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)           # evict the weakest of k+1
        # The root is the smallest of the k largest = the k-th largest.
        return self.heap[0]

What the code is doing, line by line:

1. __init__ saves k so add knows the size limit later.
2. self.heap = [] starts an empty min-heap: self.heap[0] will always be its smallest number.
3. Feed in the starting numbers. For each nums[i]: heappush it, and if the heap now holds more than k numbers, heappop the smallest. The heap never grows past k, and what stays is always the k largest seen so far.
4. add(val) does the same two moves for one new number: push, then pop if there are k + 1.
5. return self.heap[0]. The heap holds the k largest numbers; the smallest of them is exactly the k-th largest.

Dry run on the example: KthLargest(3, [4, 5, 8, 2]), then add(3), add(5), add(10), add(9), add(4). Heap contents are listed in sorted order for readability.

The returned values are 4, 5, 5, 8, 8, matching LeetCode's expected output.

Edge cases to test:

• The initial array has fewer than k elements.
• Adding values smaller than everything in the heap.
• Negative values.

Complexity: O(n log k) to build, O(log k) per add, O(k) space.

Problem: Return the k most frequent words, sorted by frequency (highest first). Break ties alphabetically.

Solve it on LeetCode ↗

Constraints: 1 ≤ words.length ≤ 500 · 1 ≤ words[i].length ≤ 10 · words[i] consists of lowercase English letters. · k is in the range [1, The number of unique words[i]]

From brute force to the pattern: Sorting all distinct words with the combined key is O(u log u) and is perfectly fine. A heap of size k with a careful comparator brings it to O(u log k).

Spot it: "k most frequent" → count, then a heap. The twist is the exact output order, including ties.

Approach:

1. Count the words.
2. Build tuples (-freq, word). The smallest tuple is the most frequent word, and alphabetical order breaks ties for free.
3. heapify all of them in O(m).
4. Pop k times. Pops come out in exactly the required order.

import heapq
from typing import List

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        # Step 1: count each word.
        counts = {}
        for i in range(len(words)):
            word = words[i]
            if word not in counts:
                counts[word] = 0
            counts[word] = counts[word] + 1

        # Step 2: build (-frequency, word) tuples. heapq is a MIN-heap, so the
        # smallest tuple comes out first: the most frequent word (most
        # negative number). On a frequency tie Python compares the words,
        # and the alphabetically smaller word is the smaller tuple.
        heap = []
        for word in counts:
            frequency = counts[word]
            heap.append((-frequency, word))
        heapq.heapify(heap)                    # rearrange the list into a heap, O(m)

        # Step 3: pop k times. heappop returns the smallest tuple each time,
        # so the words come out in exactly the required order.
        result = []
        for i in range(k):
            entry = heapq.heappop(heap)
            result.append(entry[1])            # field 1 of the tuple is the word
        return result

What the code is doing, line by line:

1. Count the words into the dictionary counts: the first time a word appears, set it to 0, then add 1.
2. Make one tuple per distinct word: (-frequency, word). Python compares tuples field by field, so a higher frequency (more negative number) makes a smaller tuple. If two frequencies are equal, it compares the words, and "i" < "love" alphabetically. One tuple encodes both sorting rules.
3. heapq.heapify(heap) rearranges the list in place so the smallest tuple is at heap[0]. It takes O(m) for m distinct words, cheaper than pushing them one at a time.
4. Pop k times. Each heappop removes and returns the smallest remaining tuple, i.e. the next word in the required order. Take field [1] (the word) and append it.
5. Return the list of k words, already in the right order.

Dry run on the example: words = ["i","love","leetcode","i","love","coding"], k = 2. Counts: i → 2, love → 2, leetcode → 1, coding → 1. Heap tuples in sorted order: (-2,'i'), (-2,'love'), (-1,'coding'), (-1,'leetcode').

After k = 2 pops the answer is ["i", "love"].

Edge cases to test:

• Ties in frequency must be ordered alphabetically.
• k equals the number of distinct words.
• One word repeated.

Complexity: O(n + k log m) time (m = distinct words), O(m) space. A size-k heap with a reversed comparator gives O(n log k), but it's trickier to get right.

Problem: Given a sorted array, return the k values closest to x, in ascending order. On a tie in distance, the smaller value wins.

Solve it on LeetCode ↗

Constraints: 1 ≤ k ≤ arr.length · 1 ≤ arr.length ≤ 10⁴ · arr is sorted in ascending order. · -10⁴ ≤ arr[i], x ≤ 10⁴

From brute force to the pattern: Sorting by distance to x is O(n log n); shrinking a window from both ends is O(n − k). Binary-searching the start of the window is O(log(n − k) + k).

Spot it: It looks like Top K (heap by distance works in O(n log k)), but the input is sorted, so the answer is a contiguous window. Binary search for where that window starts (see Modified Binary Search).

Approach:

1. The window start low ranges over [0, n − k].
2. For a candidate start mid, compare the two values competing at the window's edges: arr[mid] (inside) and arr[mid + k] (just outside on the right).
3. If x − arr[mid] > arr[mid + k] − x, the left value is worse, so the window must start later: low = mid + 1. Otherwise high = mid.
4. Return the k values arr[low] through arr[low + k − 1].

from typing import List

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        # The answer is k neighbours in a row. Binary search for where that
        # window starts. It can start anywhere from 0 to len(arr) - k.
        low = 0
        high = len(arr) - k
        while low < high:
            mid = (low + high) // 2
            # Compare the window's first value arr[mid] with the value just
            # past its right end, arr[mid + k]. Only one of them can be in.
            distance_left = x - arr[mid]
            distance_right = arr[mid + k] - x
            if distance_left > distance_right:
                # The left value is farther away: the window must start later.
                low = mid + 1
            else:
                # The left value is at least as close: start at mid or earlier.
                high = mid
        # Copy the k values starting at `low`.
        result = []
        for i in range(low, low + k):
            result.append(arr[i])
        return result

What the code is doing, line by line:

1. low = 0, high = len(arr) - k. The window of k values can start at index 0 at the earliest and at len(arr) - k at the latest (so it doesn't run off the end).
2. while low < high. Keep halving the range of possible starts until only one is left.
3. mid = (low + high) // 2. Try the start in the middle.
4. The two distances. A window starting at mid contains arr[mid] but not arr[mid + k]. Sliding it one step right would swap them. distance_left = x - arr[mid] and distance_right = arr[mid + k] - x measure how far each is from x (we skip abs() on purpose: the signed version also handles x lying outside the window correctly).
5. If the left value is farther, the best window must start after mid: low = mid + 1.
6. Otherwise (closer, or a tie, where the smaller value wins) the best start is mid or earlier: high = mid.
7. Copy the window. Append arr[low] … arr[low + k - 1] to result. The input is sorted, so the result is already in ascending order.

Dry run on the example: arr = [1, 2, 3, 4, 5], k = 4, x = 3. Start: low = 0, high = 5 - 4 = 1.

Now low = high = 0, so the loop stops. The window starts at 0 and the answer is [1, 2, 3, 4].

Edge cases to test:

• x smaller than every element → the first k.
• x larger than every element → the last k.
• Ties: the smaller element wins.

Complexity: O(log(n − k) + k) time, O(1) extra space.

Problem: Rearrange the letters of s so that no two adjacent letters are equal. Return any valid arrangement, or "" if it's impossible.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 500 · s consists of lowercase English letters.

From brute force to the pattern: Trying permutations is factorial. A greedy max-heap always places the most frequent available letter, holding the previous one back for a step: O(n log 26).

Spot it: Greedy: always place the letter with the most copies left, but never the same letter twice in a row. "Repeatedly take the current max" → max-heap.

Approach:

1. Build a max-heap of (-count, letter).
2. Pop the most frequent letter and append it to the output.
3. Push back the letter used in the previous step (held out for one turn so it can't repeat), if it still has copies.
4. Hold the current letter out (with its count decremented) for the next round.
5. If the output is shorter than s, the heap ran dry while a letter was held out, so it's impossible: return "".

import heapq

class Solution:
    def reorganizeString(self, s: str) -> str:
        # Step 1: count each letter.
        counts = {}
        for i in range(len(s)):
            letter = s[i]
            if letter not in counts:
                counts[letter] = 0
            counts[letter] = counts[letter] + 1

        # Step 2: a MAX-heap of (-count, letter). heapq is a min-heap, so
        # negative counts make the most frequent letter come out first.
        heap = []
        for letter in counts:
            heap.append((-counts[letter], letter))
        heapq.heapify(heap)                    # rearrange the list into a heap

        output = []
        held = None                            # letter used last step: not allowed right now
        while len(heap) > 0:
            # Take the most frequent letter that isn't being held out.
            entry = heapq.heappop(heap)
            negative_count = entry[0]
            letter = entry[1]
            output.append(letter)
            # Last step's letter is allowed again, so put it back.
            if held is not None:
                heapq.heappush(heap, held)
            # One copy used. Counts are negative, so "one fewer" means +1.
            negative_count = negative_count + 1
            # Hold this letter out for one turn if it still has copies left.
            if negative_count < 0:
                held = (negative_count, letter)
            else:
                held = None

        # If we couldn't place every letter, a letter was stuck in `held`.
        if len(output) != len(s):
            return ""
        # Glue the letters together into one string.
        result = ""
        for i in range(len(output)):
            result = result + output[i]
        return result

What the code is doing, line by line:

1. Count the letters into the dictionary counts (first sighting sets 0, then add 1).
2. Build the max-heap. Append (-count, letter) for each letter and heapify. The most frequent letter has the most negative first field, so it is the smallest tuple and sits at heap[0].
3. output = [], held = None. output collects letters in order. held is the letter we just placed: it sits outside the heap for one turn so it can't be picked twice in a row.
4. Pop the best letter. heappop returns the tuple with the most copies left among the letters not held. Read its two fields by index and append the letter.
5. Release the held letter. Now that a different letter has been placed, last turn's letter is safe to use again, so push it back.
6. Use up one copy. negative_count + 1 moves the count one step toward 0.
7. Hold the current letter. If it still has copies (count still below 0), park it in held; otherwise it's finished and held becomes None.
8. Check for failure. The loop stops when the heap is empty. If a letter was still parked in held, it never got placed, so output is shorter than s and the answer is "".
9. Glue the letters. Add each letter onto result one at a time and return it.

Dry run on the example: s = "aab". Counts: a → 2, b → 1. Start: heap = [(-2, 'a'), (-1, 'b')], held = None.

output has 3 letters, the same as s, so the answer is "aba". (For "aaab" the heap runs dry while an a is still held, so the answer is "".)

Edge cases to test:

• Impossible inputs, e.g. "aaab" → "".
• A single letter.
• Two letters with equal counts.

Complexity: O(n log σ) time where σ = alphabet size (≤ 26), O(σ) space.

Problem: Every row and every column of an n × n matrix is sorted ascending. Return the k-th smallest element overall.

Solve it on LeetCode ↗

Constraints: n == matrix.length == matrix[i].length · 1 ≤ n ≤ 300 · -10⁹ ≤ matrix[i][j] ≤ 10⁹ · All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order. · 1 ≤ k ≤ n²

From brute force to the pattern: Flattening and sorting is O(n² log n). A heap of row fronts is O(k log n); binary search on the value range with a staircase count is O(n log(max − min)).

Spot it: Each row is a sorted list, so this is "merge n sorted lists and stop at the k-th item": a k-way merge with a min-heap. (Binary search on the value also works.)

Approach:

1. Push the first element of each row (at most k rows matter) as (value, row, col).
2. Pop the smallest k − 1 times. After each pop, push the next element in the same row.
3. The heap's root is now the k-th smallest.

import heapq
from typing import List

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        size = len(matrix)
        # Only the first k rows can contain the k smallest values.
        rows_to_use = min(size, k)
        # The heap holds (value, row, col) for the front of each row.
        # heappush adds a tuple; heappop removes the one with the smallest value.
        heap = []
        for row in range(rows_to_use):
            heapq.heappush(heap, (matrix[row][0], row, 0))

        # Throw away the k-1 smallest values, one at a time.
        for step in range(k - 1):
            entry = heapq.heappop(heap)
            row = entry[1]
            col = entry[2]
            # The next value in that same row now joins the race.
            if col + 1 < size:
                heapq.heappush(heap, (matrix[row][col + 1], row, col + 1))

        # The smallest value left is the k-th smallest overall.
        smallest_entry = heap[0]
        return smallest_entry[0]

What the code is doing, line by line:

1. size = len(matrix). The matrix is size × size.
2. rows_to_use = min(size, k). The first value of row k+1 is already bigger than or equal to the first values of the k rows above it (columns are sorted), so rows past k can never hold one of the k smallest.
3. Seed the heap. Push (matrix[row][0], row, 0) for each row: the row's first (smallest) value plus where it lives, so we know which value comes next.
4. The for step in range(k - 1) loop. Each heappop removes the smallest value still in play. After removing k − 1 of them, the next smallest is the answer.
5. Read the position. row = entry[1], col = entry[2] say where the removed value was.
6. Push its right-hand neighbour. If the row has another column, push (matrix[row][col + 1], row, col + 1). This is exactly the "merge k sorted lists" move: each row keeps one representative in the heap.
7. Return heap[0][0]. The root is the smallest remaining value, which is the k-th smallest overall.

Dry run on the example: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8. Start: heap = [(1,0,0), (10,1,0), (12,2,0)]. Heap contents are listed in sorted order for readability.

Seven values (k − 1) were thrown away. heap[0][0] is 13, the 8th smallest.

Edge cases to test:

• k = 1 → the top-left corner.
• k = n² → the bottom-right corner.
• Duplicate values.

Complexity: O(k log min(n, k)) time, O(min(n, k)) space.

Problem: CPU tasks are letters. Each unit of time runs one task or stays idle. The same letter must be at least n units apart. Return the minimum total time.

Solve it on LeetCode ↗

Constraints: 1 ≤ tasks.length ≤ 10⁴ · tasks[i] is an uppercase English letter. · 0 ≤ n ≤ 100

From brute force to the pattern: Simulating time step by step with a heap and a cooldown queue works (O(total time · log 26)). Counting the frame formed by the most frequent task gives the answer in O(n).

Spot it: Greedy: at each tick, run the available task with the most copies left. "Most remaining" → max-heap. "Not available until time t" → a queue of cooling tasks.

Approach:

1. Max-heap of remaining counts (stored negated). An empty cooldown queue of (ready_time, count).
2. Each tick: time = time + 1. If the heap isn't empty, pop the biggest count and use one copy. If copies remain, queue it with ready_time = time + n.
3. If the queue's front is ready at this tick, push it back into the heap.
4. Stop when both the heap and the queue are empty. Return time.

import heapq
from collections import deque
from typing import List

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        # Step 1: count each task letter.
        counts = {}
        for i in range(len(tasks)):
            task = tasks[i]
            if task not in counts:
                counts[task] = 0
            counts[task] = counts[task] + 1

        # Step 2: a MAX-heap of remaining counts. heapq is a min-heap, so we
        # store NEGATIVE counts: the biggest count sits at heap[0].
        heap = []
        for task in counts:
            heap.append(-counts[task])
        heapq.heapify(heap)

        # cooling is a queue (deque = fast add on the right, fast remove on the
        # left) of (time it is allowed again, negative remaining count).
        cooling = deque()
        time = 0
        while len(heap) > 0 or len(cooling) > 0:
            time = time + 1                    # one tick of the CPU clock
            if len(heap) > 0:
                # Run one copy of the task with the most copies left.
                # Counts are negative, so "one fewer" means +1.
                remaining = heapq.heappop(heap) + 1
                if remaining != 0:
                    # Copies remain: it must rest until time + n.
                    cooling.append((time + n, remaining))
            # (If the heap was empty, this tick is an idle tick.)
            if len(cooling) > 0:
                front = cooling[0]
                if front[0] == time:
                    # Its cooldown is over: it can be picked again.
                    cooling.popleft()
                    heapq.heappush(heap, front[1])
        return time

What the code is doing, line by line:

1. Count the tasks. Walk through tasks; the first time a letter is seen, set its count to 0, then add 1. The letters themselves don't matter after this, only how many copies each has.
2. Build the max-heap. Append -count for every letter and call heapq.heapify, which rearranges the list into a heap in O(m). Because counts are negated, heap[0] is the task with the most copies left.
3. cooling = deque(). A first-in, first-out queue of tasks that just ran and must rest. Each entry is (time it may run again, negative remaining count). Tasks enter in time order, so the one ready soonest is always at the front, cooling[0].
4. The main while. Keep ticking as long as some task is either ready (in the heap) or resting (in the queue).
5. time = time + 1. One unit of time passes.
6. If a task is ready. heappop gives the most-copies task. Adding 1 to a negative count means one copy was used. If it isn't 0 yet, the task goes to the back of cooling with ready time time + n. If the heap was empty, the CPU sits idle this tick.
7. Release a rested task. If the front of cooling is ready at exactly this tick, remove it with popleft() and push its count back into the heap so it can run on the next tick.
8. return time. When both are empty every copy has run; time is the total number of ticks, idle ones included.

Dry run on the example: tasks = ["A","A","A","B","B","B"], n = 2. Start: heap = [-3, -3] (A and B, 3 copies each), cooling empty. Values shown as stored (negative counts).

Both the heap and the queue are empty, so the loop stops and the answer is 8 (the schedule A B idle A B idle A B).

Edge cases to test:

• n = 0 → len(tasks).
• Several tasks tied for the most frequent.
• Enough variety that no idle slots are needed.

Complexity: O(T log 26) where T = answer, O(26) space. (A counting formula, max(len(tasks), (maxCount−1)(n+1) + numMax), gives O(len(tasks)).)

Problem: You start with capital w and may finish at most k projects. Project i needs capital[i] to start and adds profits[i] to your capital. Maximize your final capital.

Solve it on LeetCode ↗

Constraints: 1 ≤ k ≤ 10⁵ · 0 ≤ w ≤ 10⁹ · n == profits.length · n == capital.length · 1 ≤ n ≤ 10⁵ · 0 ≤ profits[i] ≤ 10⁴ · 0 ≤ capital[i] ≤ 10⁹

From brute force to the pattern: Scanning all projects for the best affordable one each round is O(k · n). Sorting by capital plus a max-heap of affordable profits is O(n log n + k log n).

Spot it: Two heap ideas at once: projects unlock as your capital grows (sort by required capital), and among the unlocked ones you always take the most profitable (max-heap).

Approach:

1. Sort projects by required capital and keep a pointer i.
2. Repeat k times: push the profit of every project with capital ≤ w into a max-heap and advance i.
3. If the heap is empty, nothing is affordable, so stop early.
4. Otherwise pop the biggest profit and add it to w.

import heapq
from typing import List

class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        # Pair each project as (capital needed, profit).
        projects = []
        for i in range(len(profits)):
            projects.append((capital[i], profits[i]))
        # Tuples sort by their first field, so this puts the cheapest-to-start first.
        projects.sort()

        # available is a MAX-heap of the profits we can afford. heapq is a
        # min-heap, so we store NEGATIVE profits: the best profit sits at [0].
        available = []
        next_project = 0                       # first project not yet unlocked
        for round_number in range(k):
            # Unlock every project our current capital w can pay for.
            while next_project < len(projects) and projects[next_project][0] <= w:
                profit = projects[next_project][1]
                heapq.heappush(available, -profit)
                next_project = next_project + 1
            if len(available) == 0:
                break                          # nothing affordable: stop early
            # Do the most profitable affordable project.
            best_profit = -heapq.heappop(available)
            w = w + best_profit
        return w

What the code is doing, line by line:

1. Build projects. For each index i, append the pair (capital[i], profits[i]). Keeping the two numbers together means sorting can't separate a project's cost from its profit.
2. projects.sort(). Python sorts tuples by their first field (the capital needed), so the cheapest projects come first. That lets one pointer walk forward through them as our money grows.
3. available = []. A max-heap of profits we can already afford. We push -profit because heapq only gives the smallest item; the most negative number is the biggest profit.
4. next_project = 0. Index of the first project we haven't unlocked yet. It only ever moves forward.
5. The for round_number in range(k) loop. We may finish at most k projects, one per round.
6. The inner while. While the next project costs <= w, push its profit (negated) into available and move the pointer on. A project, once affordable, stays affordable, because w never goes down.
7. if len(available) == 0: break. Nothing affordable and nothing will become affordable, so more rounds can't help.
8. best_profit = -heapq.heappop(available). heappop removes the most negative entry; negating it again gives the biggest real profit.
9. w = w + best_profit. Finishing the project adds its profit to our capital, which may unlock more projects next round.
10. return w. The final capital.

Dry run on the example: k = 2, w = 0, profits = [1, 2, 3], capital = [0, 1, 1]. After sorting, projects = [(0, 1), (1, 2), (1, 3)].

After k = 2 rounds the loop ends and the answer is 4.

Edge cases to test:

• No project is affordable at the start → w.
• k larger than the number of projects.
• Projects with zero profit.

Complexity: O(n log n + k log n) time, O(n) space.

Problem: Each turn, take the two heaviest stones x ≤ y and smash them: if equal both vanish, otherwise a stone of weight y − x remains. Return the last stone's weight, or 0 if none remain.

Solve it on LeetCode ↗ · Video walkthrough ↗

Constraints: 1 ≤ stones.length ≤ 30 · 1 ≤ stones[i] ≤ 1000

From brute force to the pattern: Sorting the stones before every smash is O(n² log n). A max-heap gives the two largest in O(log n) per smash: O(n log n).

Spot it: "Repeatedly take the two largest" → a max-heap. Python's heapq is a min-heap, so store negated weights.

Approach:

1. Push every weight as a negative number; the most negative is the heaviest.
2. While at least two stones remain: pop the heaviest y and the next heaviest x (negate them back).
3. If they differ, push −(y − x).
4. Return the remaining stone's weight, or 0.

import heapq

class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # heapq is a min-heap; negating turns it into a max-heap
        heap = [-s for s in stones]
        heapq.heapify(heap)
        while len(heap) > 1:
            y = -heapq.heappop(heap)   # heaviest
            x = -heapq.heappop(heap)   # second heaviest
            if y != x:
                # the leftover piece goes back in
                heapq.heappush(heap, -(y - x))
        if heap:
            return -heap[0]
        return 0

What the code is doing, line by line:

1. heap = [-s for s in stones]: negate every weight, so the heaviest stone becomes the smallest number.
2. heapq.heapify(heap): turn the list into a heap in O(n).
3. while len(heap) > 1: a smash needs two stones.
4. y = -heapq.heappop(heap): pop and negate back to get the heaviest; then x, the second heaviest.
5. if y != x: heapq.heappush(heap, -(y - x)): equal stones both disappear; otherwise the difference survives.
6. return -heap[0] if one stone is left, else 0.

Dry run on the example:

stones = [2, 7, 4, 1, 8, 1] (LeetCode Example 1). Returns 1.

One stone of weight 1 remains.

Edge cases to test:

• A single stone → its weight.
• Two equal stones → 0.
• All stones equal.

Complexity: O(n log n) time, O(n) space.

Problem: Ugly numbers have no prime factors other than 2, 3 and 5 (1 counts). Return the n-th ugly number.

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 1690

From brute force to the pattern: Checking integers one by one for factors other than 2, 3, 5 needs billions of checks for n = 1690. Generating only ugly numbers, smallest first, with a heap produces exactly n of them.

Spot it: Every ugly number is a smaller ugly number times 2, 3 or 5. Generating them in increasing order means repeatedly taking the smallest unseen candidate: a min-heap (with a set to avoid duplicates like 6 = 2·3 = 3·2).

Why not another pattern? Testing every integer for ugliness is far too slow (the 1690th ugly number is about 2·10⁹). The three-pointer DP is the O(n) refinement of the same idea.

Approach:

1. Start the heap with 1 and mark it seen.
2. Pop the smallest value n − 1 times; each time push value × 2, × 3, × 5 if not seen yet.
3. The next popped value is the n-th ugly number.

import heapq

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        heap = [1]
        seen = {1}  # avoid pushing the same number twice (e.g. 6 = 2*3 = 3*2)
        for _ in range(n - 1):
            smallest = heapq.heappop(heap)  # the next ugly number in increasing order
            for factor in (2, 3, 5):
                candidate = smallest * factor
                if candidate not in seen:
                    seen.add(candidate)
                    heapq.heappush(heap, candidate)
        return heap[0]  # after n-1 pops, the smallest left is the n-th

What the code is doing, line by line:

1. The heap always contains the frontier of ugly numbers not yet output.
2. Popping gives them in increasing order, because every ugly number is generated from a smaller one before it's needed.
3. seen prevents duplicates from the different factorisations.
4. After n − 1 pops, heap[0] is the n-th ugly number.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• n = 1 → 1.
• Duplicates such as 6 and 30 must be counted once.
• n = 1690 (values exceed 2·10⁹).

Complexity: O(n log n) time, O(n) space. (The three-pointer DP is O(n).)

Problem: Implement postTweet, follow, unfollow, and getNewsFeed(userId), which returns the 10 most recent tweet ids from the user and everyone they follow, newest first.

Solve it on LeetCode ↗

Constraints: 1 ≤ userId, followerId, followeeId ≤ 500 · 0 ≤ tweetId ≤ 10⁴ · All the tweets have unique IDs. · At most 3 * 10⁴ calls will be made to postTweet, getNewsFeed, follow, and unfollow. · A user cannot follow himself.

From brute force to the pattern: Gathering every tweet from every followee and sorting them all is O(T log T) per request. A k-way heap merge only touches as many tweets as needed for the top 10.

Spot it: Each user's tweets form a list already ordered by time. The news feed is the top 10 across several sorted lists, the Merge k Sorted Lists pattern with a heap.

Why not another pattern? Collecting every tweet of every followee and sorting is O(T log T) per feed request; the heap stops after 10 tweets.

Approach:

1. Keep a global clock. tweets[user] stores (time, tweetId) in posting order; following[user] is a set.
2. getNewsFeed: push each relevant user's newest tweet onto a heap keyed by −time.
3. Pop up to 10 times; after popping a tweet, push that user's next older tweet.

import heapq
from collections import defaultdict

class Twitter:
    def __init__(self):
        self.time = 0
        self.tweets = defaultdict(list)  # user -> [(time, tweetId), ...] oldest first
        self.following = defaultdict(set)

    def postTweet(self, userId: int, tweetId: int) -> None:
        self.time = self.time + 1
        self.tweets[userId].append((self.time, tweetId))

    def getNewsFeed(self, userId: int) -> List[int]:
        users = self.following[userId] | {userId}
        heap = []
        for u in users:
            if self.tweets[u]:
                idx = len(self.tweets[u]) - 1  # newest tweet of u
                t, tid = self.tweets[u][idx]
                heapq.heappush(heap, (-t, tid, u, idx))  # max-heap on time
        feed = []
        while heap and len(feed) < 10:
            _, tid, u, idx = heapq.heappop(heap)  # the newest remaining tweet overall
            feed.append(tid)
            if idx > 0:
                t, nxt = self.tweets[u][idx - 1]  # that user's next older tweet
                heapq.heappush(heap, (-t, nxt, u, idx - 1))
        return feed

    def follow(self, followerId: int, followeeId: int) -> None:
        if followerId != followeeId:
            self.following[followerId].add(followeeId)

    def unfollow(self, followerId: int, followeeId: int) -> None:
        self.following[followerId].discard(followeeId)

What the code is doing, line by line:

1. A global counter gives every tweet a unique timestamp.
2. Each user's tweet list is sorted by time, so the feed is a k-way merge of those lists.
3. The heap holds one candidate per user (their newest unused tweet); −t makes Python's min-heap behave as a max-heap.
4. Stop after 10 tweets: only O(users + 10) heap operations per feed.
5. discard ignores unfollowing someone you don't follow.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A user following themselves (ignore it; their own tweets are always included).
• Fewer than 10 tweets in total.
• Unfollowing someone not followed.

Complexity: postTweet/follow/unfollow O(1); getNewsFeed O(f log f) for f followed users.

Problem: Given two sorted arrays, return the k pairs (u, v) (one from each) with the smallest sums.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums1.length, nums2.length ≤ 10⁵ · -10⁹ ≤ nums1[i], nums2[i] ≤ 10⁹ · nums1 and nums2 both are sorted in non-decreasing order. · 1 ≤ k ≤ 10⁴ · k ≤ nums1.length * nums2.length

From brute force to the pattern: Listing all m · n pairs and sorting costs O(mn log mn), up to 10¹⁰ pairs. The heap explores only about k pairs in increasing order of sum.

Spot it: Pair sums form a grid where every row and column is sorted. The smallest unseen pairs are always on a frontier: Kth Smallest in a Sorted Matrix with a min-heap.

Why not another pattern? Generating all m · n pairs and sorting is O(mn log mn), which is far too much when only k are needed.

Approach:

1. Push (nums1[i] + nums2[0], i, 0) for the first min(k, m) rows.
2. Pop the smallest; add the pair to the answer.
3. Push its right neighbour (i, j + 1) if it exists. Repeat until k pairs are found.

import heapq

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        heap = []
        for i in range(min(k, len(nums1))):
            heapq.heappush(heap, (nums1[i] + nums2[0], i, 0))  # first column of every row
        result = []
        while heap and len(result) < k:
            total, i, j = heapq.heappop(heap)  # the smallest remaining pair
            result.append([nums1[i], nums2[j]])
            if j + 1 < len(nums2):
                heapq.heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))  # the next pair in this row
        return result

What the code is doing, line by line:

1. Row i lists pairs (nums1[i], nums2[j]) with increasing j; each row is sorted.
2. Seeding with column 0 of each row means every row's smallest pair is on the heap.
3. After popping (i, j), its successor (i, j + 1) is the only new pair that could be next from that row.
4. Only min(k, m) rows are seeded because rows beyond the first k can't contribute to the top k.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k larger than m · n → all pairs.
• Duplicate values in the arrays.
• Negative numbers.

Complexity: O(k log k) time, O(k) space.

Problem: Sort the characters of s by decreasing frequency (equal letters grouped together). Any order among equal frequencies is fine.

Solve it on LeetCode ↗

Constraints: 1 ≤ s.length ≤ 5 * 10⁵ · s consists of uppercase and lowercase English letters and digits.

From brute force to the pattern: Repeatedly scanning for the most frequent remaining character is O(u · n). Counting once and ordering the u distinct characters is enough.

Spot it: "Order items by how often they occur" → count with a hash map, then take the most frequent first: a max-heap (or buckets by count).

Why not another pattern? Sorting the whole string with a frequency key is O(n log n); buckets indexed by count give O(n).

Approach:

1. Count the characters.
2. Push (−count, char) into a heap.
3. Pop each character and append it count times.

import heapq
from collections import Counter

class Solution:
    def frequencySort(self, s: str) -> str:
        heap = [(-cnt, ch) for ch, cnt in Counter(s).items()]
        heapq.heapify(heap)  # the most frequent character on top
        parts = []
        while heap:
            cnt, ch = heapq.heappop(heap)
            parts.append(ch * -cnt)  # write the character as many times as it appears
        return "".join(parts)

What the code is doing, line by line:

1. Counter(s) counts each character.
2. Negated counts make heapq a max-heap by frequency.
3. Each character is written out count times, so equal letters stay together.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Upper- and lowercase are different characters.
• Ties in frequency (any order is accepted).
• A single character.

Complexity: O(n + u log u) time for u distinct characters, O(n) space.

Problem: Each event [start, end] can be attended on any one day in that range; at most one event per day. Maximise the events attended.

Solve it on LeetCode ↗

Constraints: 1 ≤ events.length ≤ 10⁵ · events[i].length == 2 · 1 ≤ startDayi ≤ endDayi ≤ 10⁵

From brute force to the pattern: Matching events to days by trying combinations is exponential. The earliest-deadline-first greedy with a heap is optimal and O(n log n).

Spot it: Greedy scheduling: on each day, among the events available, attend the one that ends earliest (it has the least flexibility). The available events change every day, so keep their end days in a min-heap.

Why not another pattern? Trying assignments is exponential. Sorting by end day alone fails because an event might not have started yet.

Approach:

1. Sort events by start day.
2. Move day by day. Push the end day of every event starting today; pop events whose end day has passed.
3. If the heap isn't empty, attend the event with the smallest end day.
4. Jump day to the next start when the heap is empty, to avoid idle days.

import heapq

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        events = sorted(events)
        heap = []  # end days of events that have started and are still open
        i = 0
        day = 0
        attended = 0
        n = len(events)
        while i < n or heap:
            if not heap:
                day = max(day, events[i][0])  # skip idle days
            while i < n and events[i][0] <= day:
                heapq.heappush(heap, events[i][1])  # events that have started
                i = i + 1
            while heap and heap[0] < day:
                heapq.heappop(heap)  # expired events
            if heap:
                heapq.heappop(heap)  # attend the event ending soonest
                attended = attended + 1
                day = day + 1
        return attended

What the code is doing, line by line:

1. Events sorted by start day are added to the heap as their start day arrives.
2. Expired events (end day before today) are discarded.
3. Attending the event that ends soonest keeps the most options open for later days (an exchange argument).
4. When nothing is available, day jumps straight to the next event's start.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Overlapping identical events.
• Events lasting one day.
• Large day values with gaps (skip idle days).

Complexity: O(n log n) time, O(n) space.

Problem: Tasks [enqueueTime, processingTime] arrive over time. When idle, the CPU picks the available task with the shortest processing time (smallest index on ties). Return the processing order.

Solve it on LeetCode ↗

From brute force to the pattern: Scanning every task to find the shortest available one each time is O(n²). A heap gives the next task in O(log n).

Spot it: A simulation where the next item is the "smallest" among those currently available: a min-heap fed by tasks sorted by arrival.

Why not another pattern? Scanning all available tasks each time is O(n²).

Approach:

1. Sort task indices by enqueue time.
2. Keep time. Push every task that has arrived by time into a heap of (processing, index).
3. If the heap is empty, jump time to the next arrival. Otherwise pop a task, record it, and advance time by its processing time.

import heapq

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        order = sorted(range(len(tasks)), key=lambda i: tasks[i][0])  # by arrival time
        heap = []  # (processing time, index) of tasks that have arrived
        result = []
        time = 0
        j = 0
        while len(result) < len(tasks):
            if not heap and time < tasks[order[j]][0]:
                time = tasks[order[j]][0]  # CPU idle: jump to the next arrival
            while j < len(tasks) and tasks[order[j]][0] <= time:
                i = order[j]
                heapq.heappush(heap, (tasks[i][1], i))  # this task is now available
                j = j + 1
            proc, i = heapq.heappop(heap)  # shortest job first, smallest index on ties
            result.append(i)
            time = time + proc
        return result

What the code is doing, line by line:

1. order lists task indices by enqueue time so they can be released into the heap in time order.
2. When the CPU is idle and nothing is waiting, time jumps to the next arrival.
3. All tasks that have arrived by time are pushed; tuples compare by processing time, then by index, exactly the tie rule.
4. Running a task advances time by its processing time.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Tasks arriving at the same time.
• A long idle gap between tasks.
• Equal processing times (smallest index first).

Complexity: O(n log n) time, O(n) space.

Problem: A rhombus is a square rotated 45°, centred on grid cells (size 0 is a single cell). Return the three largest distinct rhombus border sums, in descending order.

Solve it on LeetCode ↗

Constraints: m == grid.length · n == grid[i].length · 1 ≤ m, n ≤ 50 · 1 ≤ grid[i][j] ≤ 10⁵

From brute force to the pattern: Keeping all sums and sorting them is wasteful; a size-3 set keeps just what's needed. Diagonal prefix sums could speed up each border.

Spot it: "Top 3 distinct values" among many candidates: a tiny top-k structure (a set of size ≤ 3, or a min-heap of size 3).

Why not another pattern? Diagonal prefix sums would make each border O(1) instead of O(size), which matters only for large grids; at 50 × 50 the direct sum is fast enough and much clearer.

Approach:

1. For every top corner (r, c) and every size s ≥ 0 that fits in the grid, compute the border sum.
2. Size 0 is just the cell. For s > 0, walk the four edges of the rhombus.
3. Keep a set of the three largest distinct sums.

class Solution:
    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:
        m = len(grid)
        n = len(grid[0])
        best = set()  # at most 3 largest distinct sums

        def keep(value):
            best.add(value)
            if len(best) > 3:
                best.remove(min(best))  # drop the smallest of four

        for r in range(m):
            for c in range(n):
                keep(grid[r][c])  # a rhombus of size 0
                s = 1
                while r + 2 * s < m and c - s >= 0 and c + s < n:
                    total = 0
                    for k in range(s):
                        total = total + grid[r + k][c + k]  # top corner -> right corner
                        total = total + grid[r + s + k][c + s - k]  # right corner -> bottom corner
                        total = total + grid[r + 2 * s - k][c - k]  # bottom corner -> left corner
                        total = total + grid[r + s - k][c - s + k]  # left corner -> top corner
                    keep(total)
                    s = s + 1
        return sorted(best, reverse=True)

What the code is doing, line by line:

1. (r, c) is the top corner; size s puts the other corners at (r + s, c ± s) and (r + 2s, c).
2. Each edge walk adds s cells, starting at one corner and stopping before the next, so every border cell is added exactly once.
3. keep holds at most three distinct values, dropping the smallest when a fourth arrives.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Fewer than three distinct sums (e.g. all equal values).
• A single row → only size-0 rhombi.
• Duplicate sums count once.

Complexity: O(m · n · min(m, n)²) time (fine for 50 × 50), O(1) extra space.

Problem: Records (timestamp, price) arrive out of order and may correct earlier records. Support update, current (price at the latest timestamp), maximum and minimum over the current records.

Solve it on LeetCode ↗

Constraints: 1 ≤ timestamp, price ≤ 10⁹ · At most 10⁵ calls will be made in total to update, current, maximum, and minimum. · current, maximum, and minimum will be called only after update has been called at least once.

From brute force to the pattern: Recomputing the max and min over all timestamps on each query is O(n) per call. Heaps with lazy deletion make queries amortised O(log n).

Spot it: Min and max of a changing collection → heaps. Corrections make old heap entries stale; instead of deleting them, check each top against the hash map and discard it if it no longer matches (lazy deletion).

Why not another pattern? Rescanning all prices for maximum/minimum is O(n) per call. A sorted container also works but isn't built into Python.

Approach:

1. price_at[t] stores the latest price for each timestamp; latest tracks the largest timestamp.
2. update writes the map and pushes (price, t) into a min-heap and (−price, t) into a max-heap.
3. maximum: while the max-heap's top disagrees with price_at[t], pop it. The remaining top is correct. Same for minimum.

import heapq

class StockPrice:
    def __init__(self):
        self.price_at = {}  # timestamp -> current price
        self.latest = 0
        self.min_heap = []  # (price, timestamp)
        self.max_heap = []  # (-price, timestamp)

    def update(self, timestamp: int, price: int) -> None:
        self.price_at[timestamp] = price  # a correction simply overwrites
        self.latest = max(self.latest, timestamp)
        heapq.heappush(self.min_heap, (price, timestamp))
        heapq.heappush(self.max_heap, (-price, timestamp))

    def current(self) -> int:
        return self.price_at[self.latest]

    def maximum(self) -> int:
        while -self.max_heap[0][0] != self.price_at[self.max_heap[0][1]]:
            heapq.heappop(self.max_heap)  # stale entry from a corrected record
        return -self.max_heap[0][0]

    def minimum(self) -> int:
        while self.min_heap[0][0] != self.price_at[self.min_heap[0][1]]:
            heapq.heappop(self.min_heap)  # stale entry
        return self.min_heap[0][0]

What the code is doing, line by line:

1. The hash map always has the true price for each timestamp, so current is a lookup.
2. Every update pushes a new heap entry; old entries for a corrected timestamp stay in the heaps but no longer match the map.
3. maximum and minimum pop stale tops until the top agrees with the map: lazy deletion.
4. Each entry is popped at most once, so the cost is amortised O(log n) per call.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Correcting the current maximum (stale tops must be skipped).
• Records arriving out of order (current uses the largest timestamp, not the last update).
• The same timestamp corrected several times.

Complexity: update O(log n); current O(1); maximum/minimum amortised O(log n); O(n) space.

Problem: Worker i needs t·1 + t·2 + … + t·x seconds to remove x units (with t = workerTimes[i]). Workers work in parallel. Return the minimum time to remove mountainHeight units.

Solve it on LeetCode ↗

Constraints: 1 ≤ mountainHeight ≤ 10⁵ · 1 ≤ workerTimes.length ≤ 10⁴ · 1 ≤ workerTimes[i] ≤ 10⁶

From brute force to the pattern: Trying every split of the height among the workers is exponential. The greedy assignment with a heap is O(H log W), and binary search on the time is an alternative.

Spot it: Assign units one at a time, always to the worker whose total time after taking one more unit is smallest. That's a greedy choice driven by a min-heap; the answer is the largest finishing time among the assigned units.

Why not another pattern? Binary search on the answer T (how many units each worker can do in T seconds, via the quadratic formula) is the other standard solution, O(W log T).

Approach:

1. For each worker push (t × 1, t, 1): the finishing time if they do their first unit.
2. Repeat mountainHeight times: pop the smallest finishing time f; the answer is at least f.
3. That worker now has x units; push their next finishing time t · (x + 1)(x + 2) / 2.

import heapq

class Solution:
    def minNumberOfSeconds(self, mountainHeight: int, workerTimes: List[int]) -> int:
        heap = [(t, t, 1) for t in workerTimes]  # (total time if they do x units, t, x)
        heapq.heapify(heap)
        answer = 0
        for _ in range(mountainHeight):
            finish, t, x = heapq.heappop(heap)  # the worker who would finish this unit earliest
            answer = max(answer, finish)
            nxt = x + 1
            heapq.heappush(heap, (t * nxt * (nxt + 1) // 2, t, nxt))  # their time for one more unit
        return answer

What the code is doing, line by line:

1. A worker who removes x units spends t · x(x + 1)/2 seconds in total.
2. The heap holds, for each worker, the total time if they take one more unit.
3. Giving the next unit to the worker with the smallest such time keeps the maximum as low as possible.
4. answer is the largest finishing time among all assigned units: the overall time.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• A single worker → t · H(H + 1)/2.
• One very fast worker among slow ones.
• Large times (Python integers don't overflow).

Complexity: O((H + W) log W) time for height H and W workers, O(W) space.

Problem: Rearrange s so that equal letters are at least k positions apart. Return any valid result, or "" if impossible.

Solve it on LeetCode ↗ (Premium)

Constraints: 1 ≤ s.length ≤ 3 * 10⁵ · s consists of only lowercase English letters · 0 ≤ k ≤ s.length

From brute force to the pattern: Searching permutations is factorial. The greedy places the most constrained letter as early as allowed, which is optimal.

Spot it: Greedy: always place the most frequent available letter (max-heap), but a letter just used must wait k turns before it becomes available again (a queue). Like Task Scheduler and Reorganize String.

Why not another pattern? Trying permutations is factorial. Placing letters round-robin by frequency works for some inputs but needs care; the heap + queue greedy is the standard safe method.

Approach:

1. Count letters; push (−count, letter) into a max-heap.
2. Repeatedly pop the most frequent available letter, append it, and put it in a waiting queue with its remaining count.
3. Once the queue holds k letters, the oldest one has waited long enough: push it back into the heap (if it has copies left).
4. If the heap runs dry before the result is complete, return "".

import heapq
from collections import Counter, deque

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        if k <= 1:
            return s  # any order works
        heap = [(-cnt, ch) for ch, cnt in Counter(s).items()]
        heapq.heapify(heap)  # most frequent letter first
        waiting = deque()  # letters cooling down, oldest first
        result = []
        while heap:
            cnt, ch = heapq.heappop(heap)
            result.append(ch)
            waiting.append((cnt + 1, ch))  # one copy used (counts are negative)
            if len(waiting) >= k:
                c, w = waiting.popleft()  # placed k letters ago: available again
                if c < 0:
                    heapq.heappush(heap, (c, w))
        return "".join(result) if len(result) == len(s) else ""

What the code is doing, line by line:

1. Counts are stored negated so heapq pops the most frequent letter.
2. After placing a letter it goes into waiting; it can't be used again until k − 1 other letters follow it.
3. When waiting reaches size k, its oldest letter is released back to the heap (if copies remain).
4. If the heap empties while letters are still waiting, no valid arrangement exists.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k = 0 or 1 → s itself.
• Impossible inputs, e.g. "aaabc", k = 3 → "".
• All letters distinct → always possible.

Complexity: O(n log 26) = O(n) time, O(1) extra space for the 26 letters.

Problem: A car starts with startFuel and must reach target. Stations [position, fuel] lie along the way. Return the minimum number of stops, or −1.

Solve it on LeetCode ↗

Constraints: 1 ≤ target, startFuel ≤ 10⁹ · 0 ≤ stations.length ≤ 500 · 1 ≤ positioni < positioni+1 < target · 1 ≤ fueli < 10⁹

From brute force to the pattern: Trying every subset of stations is exponential; DP on (station, number of stops) is O(n²). The heap greedy makes each stop as valuable as possible: O(n log n).

Spot it: Pretend you can decide later which passed stations you stopped at. When fuel runs out, the best choice is the station with the most fuel among those already passed: a max-heap.

Why not another pattern? A DP over (stations, stops) is O(n²). Greedy with a heap is O(n log n) and provably optimal: each stop adds as much range as possible.

Approach:

1. Walk through stations in order (plus the target as a final "station").
2. Before reaching a station, while the fuel can't get there, pop the largest fuel from the heap (one more stop). If the heap is empty, return −1.
3. On reaching a station, push its fuel into the heap (available for later).

import heapq

class Solution:
    def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
        heap = []  # fuel of stations we've passed (negated for a max-heap)
        reach = startFuel  # how far we can drive with the stops chosen so far
        stops = 0
        for position, fuel in stations + [[target, 0]]:
            while reach < position:
                if not heap:
                    return -1  # stuck and no passed station left to use
                reach = reach + -heapq.heappop(heap)  # stop retroactively at the richest station
                stops = stops + 1
            heapq.heappush(heap, -fuel)  # this station is now available
        return stops

What the code is doing, line by line:

1. reach is the farthest point reachable with the stops chosen so far.
2. Appending [target, 0] makes reaching the target the last check.
3. If the next position is out of reach, we "go back in time" and stop at the passed station with the most fuel; that adds the most range per stop.
4. Each station is pushed once and popped at most once.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Enough start fuel → 0.
• No stations and not enough fuel → −1.
• A station exactly at the reach limit (reaching it with 0 fuel is fine).

Complexity: O(n log n) time, O(n) space.

Problem: Delete the fewest elements of nums so that its smallest remaining element divides every element of numsDivide. Return that count or −1.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length, numsDivide.length ≤ 10⁵ · 1 ≤ nums[i], numsDivide[i] ≤ 10⁹

From brute force to the pattern: For each candidate, checking it against all of numsDivide is O(n · m). The GCD turns that into one % per candidate, and trying candidates from smallest up finds the answer with the fewest deletions.

Spot it: "Divides every element" collapses to "divides their GCD". Then you want the smallest value of nums that divides the GCD, and must delete everything smaller: take values from smallest up (a min-heap or sorting).

Why not another pattern? Testing each candidate against every element of numsDivide is O(n · m); the GCD reduces that to one modulo per candidate.

Approach:

1. g = gcd of all numsDivide.
2. Heapify nums; pop values in increasing order, counting deletions.
3. The first value x with g % x == 0 is the answer: the number of smaller values popped before it.
4. If none divides g, return −1.

import heapq
from math import gcd

class Solution:
    def minOperations(self, nums: List[int], numsDivide: List[int]) -> int:
        g = 0
        for x in numsDivide:
            g = gcd(g, x)  # x divides every element <=> x divides their gcd
        heap = list(nums)
        heapq.heapify(heap)
        deletions = 0
        while heap:
            smallest = heapq.heappop(heap)
            if g % smallest == 0:
                return deletions  # everything smaller has been deleted
            deletions = deletions + 1  # this value can't be the smallest: delete it
        return -1

What the code is doing, line by line:

1. gcd(0, x) = x, so starting at g = 0 and folding in each number gives the GCD of the whole list.
2. A number divides all of numsDivide exactly when it divides g.
3. Popping from a min-heap tries candidates from smallest up; every rejected value must be deleted (equal copies are deleted too, since they also fail).

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No value divides the GCD → −1.
• The minimum of nums already works → 0.
• Duplicates of a failing value (all must be deleted).

Complexity: O(m log V + n log n) time, O(n) space.

Problem: Meetings [start, end) (distinct starts) are assigned in start order to the lowest-numbered free room among n rooms; if none is free, the meeting waits for the room that frees up first and keeps its duration. Return the room that held the most meetings (lowest number on ties).

Solve it on LeetCode ↗

Constraints: 1 ≤ n ≤ 100 · 1 ≤ meetings.length ≤ 10⁵ · meetings[i].length == 2 · 0 ≤ starti < endi ≤ 5 * 10⁵ · All the values of starti are unique.

From brute force to the pattern: Checking every room for every meeting is O(m · n). Two heaps give both choices in O(log n) per meeting.

Spot it: A simulation where you repeatedly need "the lowest free room" and "the room that becomes free first": two min-heaps.

Why not another pattern? Scanning all rooms for each meeting is O(m · n); that's fine for small n but the heaps make it O(m log n).

Approach:

1. Sort meetings by start. free = heap of room numbers; busy = heap of (end_time, room).
2. For each meeting, release every busy room whose end time ≤ the start into free.
3. If a room is free, take the lowest one; the meeting runs [start, end).
4. Otherwise pop the earliest-ending busy room; the meeting starts when it frees up and keeps its duration.
5. Count meetings per room; return the room with the highest count (lowest number on ties).

import heapq

class Solution:
    def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
        free = list(range(n))  # free room numbers (already a valid heap)
        busy = []  # (end time, room)
        count = [0] * n
        for start, end in sorted(meetings):
            while busy and busy[0][0] <= start:
                _, room = heapq.heappop(busy)
                heapq.heappush(free, room)  # this room is free by the time the meeting starts
            if free:
                room = heapq.heappop(free)  # lowest-numbered free room
                heapq.heappush(busy, (end, room))
            else:
                free_at, room = heapq.heappop(busy)  # wait for the earliest room to free up
                heapq.heappush(busy, (free_at + (end - start), room))  # same duration, delayed
            count[room] = count[room] + 1
        return count.index(max(count))  # most meetings, lowest room number on ties

What the code is doing, line by line:

1. free is sorted, which is already a valid min-heap of room numbers.
2. Before placing a meeting, every room whose meeting ended by start is returned to free.
3. With a free room available, the lowest-numbered one is used.
4. Otherwise the meeting waits for the earliest-ending room; busy orders by end time and then room number, matching the rules.
5. count.index(max(count)) returns the smallest room number among the busiest.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All meetings overlap (every meeting after the first n is delayed).
• Ties in end time (lower room number first).
• One room.

Complexity: O(m log m + m log n) time, O(n) space.

Problem: Return the median of every window of size k.

Solve it on LeetCode ↗

Constraints: 1 ≤ k ≤ nums.length ≤ 10⁵ · -2³¹ ≤ nums[i] ≤ 2³¹ - 1

From brute force to the pattern: Sorting every window is O(n · k log k); two heaps with lazy deletion are O(n log n).

Spot it: Medians of a changing collection → two heaps (as in Find Median from Data Stream). Heaps can't delete arbitrary values, so mark outgoing values in a counter and remove them lazily when they reach a heap top.

Why not another pattern? Sorting each window is O(n · k log k); a sorted list with insort is O(n · k).

Approach:

1. low (max-heap, stored negated) holds the smaller half, high the larger; low may have one extra.
2. Slide: add the new value to the right heap, mark the outgoing one for deletion, and rebalance using the valid sizes.
3. Clean both heap tops of deleted values; the median is low's top (odd k) or the average of both tops.

import heapq
from collections import Counter

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        low, high = [], []  # low: max-heap (negated) of the smaller half; high: min-heap of the larger half
        dead = Counter()  # values that left the window but still sit inside a heap

        def prune(heap, sign):
            while heap and dead[sign * heap[0]]:
                dead[sign * heap[0]] -= 1  # remove it now that it reached the top
                heapq.heappop(heap)

        for x in sorted(nums[:k]):
            heapq.heappush(low, -x)
        for _ in range(k // 2):
            heapq.heappush(high, -heapq.heappop(low))  # low keeps the extra element when k is odd

        def median():
            return float(-low[0]) if k % 2 else (-low[0] + high[0]) / 2

        result = [median()]
        for i in range(k, len(nums)):
            new, old = nums[i], nums[i - k]
            balance = 0  # > 0: low gained a valid element, < 0: high did
            if new <= -low[0]:
                heapq.heappush(low, -new)
                balance += 1
            else:
                heapq.heappush(high, new)
                balance -= 1
            dead[old] += 1
            balance += -1 if old <= -low[0] else 1  # the outgoing value lived in low or high
            if balance > 0:
                heapq.heappush(high, -heapq.heappop(low))  # low has one too many valid values
            elif balance < 0:
                heapq.heappush(low, -heapq.heappop(high))
            prune(low, -1)
            prune(high, 1)
            result.append(median())
        return result

What the code is doing, line by line:

1. balance tracks how the valid sizes changed: +1 when low gains, −1 when it loses (the outgoing value counts against whichever heap held it).
2. Moving one top across restores the size invariant; dead values may still be inside the heaps but are never at a top when reading the median.
3. An outgoing value equal to low's top is treated as living in low, which is consistent with where equal values are inserted.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k = 1 (each element).
• Even k (average of two).
• Duplicates leaving the window.

Complexity: O(n log n) time (heaps can hold up to n stale entries), O(n) space.

Problem: Climbing to a taller building costs bricks equal to the height difference, or one ladder. Return the furthest index reachable.

Solve it on LeetCode ↗

Constraints: 1 ≤ heights.length ≤ 10⁵ · 1 ≤ heights[i] ≤ 10⁶ · 0 ≤ bricks ≤ 10⁹ · 0 ≤ ladders ≤ heights.length

From brute force to the pattern: Trying every ladder assignment is exponential; binary search + sorting is O(n log² n); the heap is O(n log L).

Spot it: Ladders should go to the largest climbs seen so far. Keep the climbs using ladders in a min-heap of size ladders; when it overflows, the smallest of them is paid with bricks instead.

Why not another pattern? Deciding greedily at each climb (bricks first) can waste bricks on a big climb a ladder should have taken.

Approach:

1. For each climb d > 0: push it.
2. If the heap has more than ladders climbs, pop the smallest and pay it in bricks.
3. If bricks go negative, stop: the answer is i.

import heapq

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        ladder_climbs = []  # the climbs currently covered by ladders (min-heap)
        for i in range(len(heights) - 1):
            d = heights[i + 1] - heights[i]
            if d <= 0:
                continue  # going down is free
            heapq.heappush(ladder_climbs, d)
            if len(ladder_climbs) > ladders:
                bricks -= heapq.heappop(ladder_climbs)  # smallest climb gets bricks instead
                if bricks < 0:
                    return i  # can't make this step
        return len(heights) - 1

What the code is doing, line by line:

1. At every point, the heap holds the ladders biggest climbs so far, which is the best use of ladders for that prefix.
2. Bricks pay for all other climbs; once they run out, building i + 1 is unreachable.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• No climbs (reach the end).
• Zero ladders.
• Bricks exactly enough.

Complexity: O(n log L) time, O(L) space.

Problem: A colour with x balls left sells for x. Sell orders balls for the maximum total (mod 10⁹ + 7).

Solve it on LeetCode ↗

Constraints: 1 ≤ inventory.length ≤ 10⁵ · 1 ≤ inventory[i] ≤ 10⁹ · 1 ≤ orders ≤ min(sum(inventory[i]), 10⁹)

From brute force to the pattern: Heap pops per ball are O(orders log n); level batching is O(n log n).

Spot it: Greedy: always sell the currently most valuable ball (the top-k / max-heap idea). Selling one ball at a time is too slow, so sort descending and lower the top group of colours level by level, using arithmetic series.

Why not another pattern? A heap popping one ball at a time is O(orders log n) with orders up to 10⁹.

Approach:

1. Sort descending; append 0. Keep width = colours at the current top value.
2. Lowering the top width colours from cur to nxt sells width · (cur − nxt) balls; if that's more than the remaining orders, sell full rows plus a partial row and stop.
3. Otherwise add width · (cur + nxt + 1)(cur − nxt)/2 and continue.

class Solution:
    def maxProfit(self, inventory: List[int], orders: int) -> int:
        MOD = 10**9 + 7
        inv = sorted(inventory, reverse=True) + [0]
        total = 0
        width = 1  # colours currently at the top value
        for i in range(len(inv) - 1):
            cur, nxt = inv[i], inv[i + 1]
            if cur > nxt:
                if width * (cur - nxt) >= orders:
                    rows, extra = divmod(orders, width)  # full levels, then a partial level
                    total += width * (cur + cur - rows + 1) * rows // 2
                    total += extra * (cur - rows)
                    return total % MOD
                total += width * (cur + nxt + 1) * (cur - nxt) // 2  # sell cur, cur-1, ..., nxt+1 from each
                orders -= width * (cur - nxt)
            width += 1
        return total % MOD

What the code is doing, line by line:

1. Selling from the highest counts first is optimal: any other order sells a cheaper ball while a pricier one is available.
2. (cur + nxt + 1)(cur − nxt)/2 is the sum cur + … + (nxt + 1) per colour.
3. The partial level sells extra balls at the next price cur − rows.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• One colour.
• Orders end in the middle of a level.
• All equal counts.

Complexity: O(n log n) time, O(1) extra space.

Problem: Repeatedly take the smallest unmarked element (smallest index on ties), add it to the score, and mark it and its two neighbours.

Solve it on LeetCode ↗

Constraints: 1 ≤ nums.length ≤ 10⁵ · 1 ≤ nums[i] ≤ 10⁶

From brute force to the pattern: Finding the minimum each round is O(n²); sorting is O(n log n).

Spot it: Always the next smallest unmarked element → process in sorted order (a heap or a sort by (value, index)), skipping marked ones.

Why not another pattern? Scanning for the minimum each round is O(n²).

Approach:

1. Sort indices by (nums[i], i).
2. For each: if unmarked, add its value and mark i − 1, i, i + 1.

class Solution:
    def findScore(self, nums: List[int]) -> int:
        marked = [False] * (len(nums) + 2)  # padded so i - 1 and i + 1 are always valid (shifted by 1)
        score = 0
        for i in sorted(range(len(nums)), key=lambda i: (nums[i], i)):
            if not marked[i + 1]:
                score += nums[i]  # smallest unmarked element
                marked[i] = marked[i + 1] = marked[i + 2] = True  # it and its neighbours
        return score

What the code is doing, line by line:

1. Sorting once replaces repeatedly searching for the minimum.
2. Marked elements are skipped when their turn comes.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• Equal values (smaller index first).
• Single element.
• Already marked neighbours.

Complexity: O(n log n) time, O(n) space.

Problem: Pick at most k grid values (at most limits[i] from row i) with the maximum sum.

Solve it on LeetCode ↗

Constraints: n == grid.length == limits.length · m == grid[i].length · 1 ≤ n, m ≤ 500 · 0 ≤ grid[i][j] ≤ 10⁵ · 0 ≤ limits[i] ≤ m · 0 ≤ k ≤ min(n * m, sum(limits))

From brute force to the pattern: Choosing combinations is exponential; per-row top values + one sort is linearithmic.

Spot it: Within a row, the best limits[i] values dominate the rest. Pool those candidates and take the top k (sort or a heap).

Why not another pattern? A DP over rows and counts is unnecessary; the limits are independent per row.

Approach:

1. For each row: its limits[i] largest values.
2. Sort all candidates descending; sum the first k.

class Solution:
    def maxSum(self, grid: List[List[int]], limits: List[int], k: int) -> int:
        candidates = []
        for row, cap in zip(grid, limits):
            candidates += sorted(row, reverse=True)[:cap]  # only the best `cap` of this row can be used
        candidates.sort(reverse=True)
        return sum(candidates[:k])  # values are non-negative, so taking k is best

What the code is doing, line by line:

1. Any value outside a row's top limits[i] can be swapped for a larger one in the same row.
2. Values are non-negative, so using the full k never hurts.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k = 0.
• limits of 0.
• One row.

Complexity: O(nm log m + nm log(nm)) time, O(nm) space.

Problem: Hire exactly k workers paid proportionally to quality, each at least their minimum wage. Return the minimum total cost.

Solve it on LeetCode ↗

Constraints: n == quality.length == wage.length · 1 ≤ k ≤ n ≤ 10⁴ · 1 ≤ quality[i], wage[i] ≤ 10⁴

From brute force to the pattern: All groups of k: C(n, k); sorting + heap: O(n log n).

Spot it: In a group, everyone is paid ratio · quality where ratio is the largest wage/quality in the group. Process workers by increasing ratio; the current worker sets the ratio, and the cost is minimised by the k smallest qualities so far → a max-heap of size k (top-k pattern).

Why not another pattern? Trying every group of k is combinatorial.

Approach:

1. Sort by wage / quality.
2. Push each quality into a max-heap and add it to total; if the heap exceeds k, remove the largest.
3. When it has k, candidate total · ratio.

import heapq

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        workers = sorted((w / q, q) for q, w in zip(quality, wage))  # by pay rate
        heap = []  # max-heap (negated) of the chosen qualities
        total = 0
        best = float("inf")
        for ratio, q in workers:
            heapq.heappush(heap, -q)
            total += q
            if len(heap) > k:
                total += heapq.heappop(heap)  # drop the largest quality
            if len(heap) == k:
                best = min(best, total * ratio)  # this worker's ratio pays everyone
        return best

What the code is doing, line by line:

1. The group's ratio must be its largest ratio so nobody earns below their minimum.
2. With the ratio fixed (current worker), the cheapest group takes the smallest qualities among workers with a smaller ratio.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• k = 1 → min wage.
• k = n.
• Equal ratios.

Complexity: O(n log n) time, O(n) space.

Problem: Request i goes to server i % k or the next free one cyclically (dropped if all are busy). Return the servers that handled the most requests.

Solve it on LeetCode ↗

Constraints: 1 ≤ k ≤ 10⁵ · 1 ≤ arrival.length, load.length ≤ 10⁵ · arrival.length == load.length · 1 ≤ arrival[i], load[i] ≤ 10⁹ · arrival is strictly increasing.

From brute force to the pattern: Cyclic scanning per request is O(nk); two heaps are O(n log k) (a sorted list of free ids also works).

Spot it: Two heaps: busy servers by finish time (release those done by the arrival), and free servers. To find "the first free server at or after i % k, wrapping", store each free server j under the key i + (j − i) mod k when it's released: the smallest key is the right server.

Why not another pattern? Scanning servers cyclically for each request is O(k) per request.

Approach:

1. Initially free keys are 0..k−1.
2. At request i: release every busy server with end ≤ arrival[i], pushing it as i + (j − i) % k.
3. If none free, drop. Else pop the smallest key; the server is key % k; count it and mark it busy until arrival + load.

import heapq

class Solution:
    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:
        free = list(range(k))  # keys whose value mod k is the server id
        busy = []  # (finish time, server)
        handled = [0] * k
        for i, (t, d) in enumerate(zip(arrival, load)):
            while busy and busy[0][0] <= t:
                _, j = heapq.heappop(busy)
                heapq.heappush(free, i + (j - i) % k)  # its position in the cyclic order starting at i % k
            if not free:
                continue  # every server is busy: drop the request
            j = heapq.heappop(free) % k
            handled[j] += 1
            heapq.heappush(busy, (t + d, j))
        top = max(handled)
        return [j for j in range(k) if handled[j] == top]

What the code is doing, line by line:

1. A released server's key i + (j − i) mod k ranks it by its cyclic distance from i % k.
2. Keys pushed at earlier requests are smaller but still in the right cyclic order (a known invariant of this trick), so the minimum key is the correct next server.
3. Each request does O(log k) heap work.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• All servers busy (dropped requests).
• k = 1.
• Ties for the busiest.

Complexity: O(n log k) time, O(k) space.

Problem: Find the smallest range [a, b] that contains at least one number from each of k sorted lists.

Solve it on LeetCode ↗

Constraints: nums.length == k · 1 ≤ k ≤ 3500 · 1 ≤ nums[i].length ≤ 50 · -10⁵ ≤ nums[i][j] ≤ 10⁵ · nums[i] is sorted in non-decreasing order.

From brute force to the pattern: All candidate ranges are cubic; the heap merge is O(N log k).

Spot it: Keep one pointer per list (a k-way merge with a min-heap). The current range is [heap min, current max]. To shrink it, the only useful move is advancing the list that holds the minimum.

Why not another pattern? Trying all ranges or merging everything and sliding a window with counts is heavier.

Approach:

1. Push the first element of each list; track the max.
2. Pop the min; update the best range [min, max].
3. Push that list's next element (updating max); stop when a list runs out.

import heapq

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        heap = [(lst[0], i, 0) for i, lst in enumerate(nums)]
        heapq.heapify(heap)
        high = max(lst[0] for lst in nums)  # current range is [heap min, high]
        best = [heap[0][0], high]
        while True:
            low, i, j = heapq.heappop(heap)
            if high - low < best[1] - best[0]:
                best = [low, high]
            if j + 1 == len(nums[i]):
                return best  # this list is exhausted: no range can improve
            nxt = nums[i][j + 1]
            high = max(high, nxt)
            heapq.heappush(heap, (nxt, i, j + 1))  # move the minimum's list forward

What the code is doing, line by line:

1. Every range needs an element from each list; the heap holds the current choice.
2. Advancing any list other than the minimum's can only widen the range.
3. Ties keep the earlier (smaller-start) range because only strictly smaller widths replace it.

Dry run: use the Step through the solution player under the code. It runs this exact code on Example 1 and shows every line with the variables at that moment.

Edge cases to test:

• One list.
• Overlapping lists.
• Lists of length 1.

Complexity: O(N log k) time for N total elements, O(k) space.