Skip to content

15. Heaps#

Python's heapq module implements a min-heap only. For max-heap behavior, negate numeric keys or push (-priority, item) tuples so the smallest negated value corresponds to the largest original value.

Problems at a glance#

LC Problem
215 Kth Largest Element in an Array ↗
973 K Closest Points to Origin ↗
347 Top K Frequent Elements ↗
692 Top K Frequent Words ↗
451 Sort Characters By Frequency ↗
767 Reorganize String ↗
358 Rearrange String k Distance Apart ↗
1167 Minimum Cost to Connect Sticks ↗
857 Minimum Cost to Hire K Workers ↗
871 Minimum Number of Refueling Stops ↗
1337 The K Weakest Rows in a Matrix ↗
1046 Last Stone Weight ↗
264 Ugly Number II ↗
480 Sliding Window Median ↗
295 Find Median from Data Stream ↗
502 IPO / Maximize Capital ↗
703 Kth Largest Element in a Stream ↗
253 Meeting Rooms II ↗
759 Employee Free Time ↗
621 Task Scheduler ↗
1642 Furthest Building You Can Reach ↗
630 Course Schedule III ↗

Core patterns#

Pattern Heap choice When to use
Top K largest Min-heap of size k Keep the k best; root is the worst of the k → evict when a better candidate arrives
Top K smallest Max-heap of size k Mirror of above (negate keys in Python)
Two heaps Max-heap (lower half) + min-heap (upper half) Running median, sliding-window median
Merge streams Min-heap seeded with stream heads Ugly numbers, k-way interval merge
Scheduling / greedy Min-heap of end times or max-heap of profits Meeting rooms, refueling, task scheduler

Template — top K largest: 

import heapq
heap = []
for x in nums:
    heapq.heappush(heap, x)
    if len(heap) > k:
        heapq.heappop(heap)   # drop smallest → keep k largest
return heap[0]                # kth largest when k == len(heap)

Top 'K' Elements#

Problem 1: Kth Largest Element in an Array (Leetcode:215)#

Problem Statement

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

Example 1:

Input: nums = [3,2,1,5,6,4], k = 2
Output: 5

Example 2:

Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4

Constraints:

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
import heapq

class Solution:
    def findKthLargest(self, nums: list[int], k: int) -> int:
        heap = []
        for x in nums:
            heapq.heappush(heap, x)
            if len(heap) > k:
                heapq.heappop(heap)
        return heap[0]
Explanation:

  1. Maintain a min-heap of size k. The root is the smallest among the k largest seen so far — exactly the kth largest.
  2. For each element, push it; if size exceeds k, pop the minimum (evict the weakest of the top k).
  3. Min-heap for k largest is the standard top-k trick — never sort the full array.

Time: O(n log k) · Space: O(k)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import random

class Solution:
    def findKthLargest(self, nums: list[int], k: int) -> int:
        k = len(nums) - k  # kth largest → (n-k)th smallest (0-indexed)

        def partition(lo, hi):
            pivot = nums[random.randint(lo, hi)]
            i, j = lo, hi
            while i <= j:
                while nums[i] < pivot:
                    i += 1
                while nums[j] > pivot:
                    j -= 1
                if i <= j:
                    nums[i], nums[j] = nums[j], nums[i]
                    i += 1
                    j -= 1
            return j

        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            p = partition(lo, hi)
            if p < k:
                lo = p + 1
            elif p > k:
                hi = p - 1
            else:
                return nums[k]
        return nums[k]
Explanation:

  1. Convert to (n − k)th smallest (0-indexed) and partition like quicksort.
  2. Recurse only into the half containing index k — average O(n), no heap needed.
  3. Preferred when O(n) average is required; heap is simpler and O(n log k) worst-case.

Time: O(n) average · Space: O(1)

Problem 2: K Closest Points to Origin (Leetcode:973)#

Problem Statement

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Example 1:


Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation: The answer [[-2,4],[3,3]] would also be accepted.

Constraints:

  • 1 <= k <= points.length <= 104
  • -104 <= xi, yi <= 104
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
import heapq

class Solution:
    def kClosest(self, points: list[list[int]], k: int) -> list[list[int]]:
        heap = []  # (-dist_sq, point) → min-heap on negated dist = max-heap on dist
        for x, y in points:
            dist_sq = x * x + y * y
            heapq.heappush(heap, (-dist_sq, [x, y]))
            if len(heap) > k:
                heapq.heappop(heap)  # evict farthest among the k closest
        return [pt for _, pt in heap]
Explanation:

  1. Compare by squared distance (no sqrt needed).
  2. Use (-dist_sq, point) so Python's min-heap acts as a max-heap on distance — keep k closest by evicting the farthest when size > k.
  3. Classic top-k smallest via negation trick.

Time: O(n log k) · Space: O(k)

1
2
3
4
class Solution:
    def kClosest(self, points: list[list[int]], k: int) -> list[list[int]]:
        points.sort(key=lambda p: p[0] * p[0] + p[1] * p[1])
        return points[:k]
Explanation:

  1. Sort all points by squared distance and take the first k.
  2. Simpler when k is close to n or heap overhead is not worth it.

Time: O(n log n) · Space: O(1) excluding output

Problem 3: Top K Frequent Elements (Leetcode:347)#

Problem Statement

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Constraints:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • k is in the range [1, the number of unique elements in the array].
  • It is guaranteed that the answer is unique.

Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
import heapq
from collections import Counter

class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        count = Counter(nums)
        heap = []
        for num, freq in count.items():
            heapq.heappush(heap, (freq, num))
            if len(heap) > k:
                heapq.heappop(heap)  # drop lowest frequency
        return [num for _, num in heap]
Explanation:

  1. Count frequencies with Counter.
  2. Min-heap stores (freq, num) — root has the smallest frequency among top k.
  3. When heap exceeds size k, pop the weakest frequency. Remaining keys are the k most frequent.

Time: O(n + m log k) where m = unique elements · Space: O(m)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
from collections import Counter

class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        count = Counter(nums)
        buckets = [[] for _ in range(len(nums) + 1)]
        for num, freq in count.items():
            buckets[freq].append(num)
        result = []
        for freq in range(len(buckets) - 1, 0, -1):
            for num in buckets[freq]:
                result.append(num)
                if len(result) == k:
                    return result
        return result
Explanation:

  1. Bucket index = frequency; frequency is at most n.
  2. Scan buckets from highest frequency down — O(n) when frequencies are bounded by n.
  3. Beats O(n log n) sorting; no heap needed.

Time: O(n) · Space: O(n)

Problem 4: Top K Frequent Words (Leetcode:692)#

Problem Statement

Given an array of strings words and an integer k, return the k most frequent strings.

Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Example 1:

Input: words = ["i","love","leetcode","i","love","coding"], k = 2
Output: ["i","love"]
Explanation: "i" and "love" are the two most frequent words.
Note that "i" comes before "love" due to a lower alphabetical order.

Example 2:

Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
Output: ["the","is","sunny","day"]
Explanation: "the", "is", "sunny" and "day" are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.

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]]

Follow-up: Could you solve it in O(n log(k)) time and O(n) extra space?

Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
import heapq
from collections import Counter

class Solution:
    def topKFrequent(self, words: list[str], k: int) -> list[str]:
        count = Counter(words)
        heap = []
        for word, freq in count.items():
            heapq.heappush(heap, (-freq, word))
            if len(heap) > k:
                heapq.heappop(heap)
        return sorted([word for _, word in heap],
                      key=lambda w: (-count[w], w))
Explanation:

  1. Push (-freq, word) — min-heap compares negated freq first (higher freq = smaller key).
  2. On equal frequency, lexicographically smaller word has smaller tuple → kept over larger word.
  3. Final sorted produces output order: highest freq first, ties broken by lex order.

Time: O(n + m log k) · Space: O(m)

1
2
3
4
5
6
7
from collections import Counter

class Solution:
    def topKFrequent(self, words: list[str], k: int) -> list[str]:
        count = Counter(words)
        return sorted(count.keys(),
                      key=lambda w: (-count[w], w))[:k]
Explanation:

  1. Sort unique words by (-frequency, word) and slice first k.
  2. Straightforward when m is small (m ≤ 500 per constraints).

Time: O(m log m) · Space: O(m)

Problem 5: Sort Characters By Frequency (Leetcode:451)#

Problem Statement

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

Example 1:

Input: s = "tree"
Output: "eert"
Explanation: 'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input: s = "cccaaa"
Output: "aaaccc"
Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input: s = "Aabb"
Output: "bbAa"
Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

Constraints:

  • 1 <= s.length <= 5 * 105
  • s consists of uppercase and lowercase English letters and digits.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
import heapq
from collections import Counter

class Solution:
    def frequencySort(self, s: str) -> str:
        count = Counter(s)
        heap = [(-freq, ch) for ch, freq in count.items()]
        heapq.heapify(heap)
        result = []
        while heap:
            neg_freq, ch = heapq.heappop(heap)
            result.append(ch * (-neg_freq))
        return "".join(result)
Explanation:

  1. Push (-freq, char) and heapify — min-heap on negated freq = max-heap on frequency.
  2. Repeatedly pop highest frequency character and append it freq times.
  3. Same negation trick as top-k, but here we drain the entire heap.

Time: O(n log m) · Space: O(m)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
from collections import Counter

class Solution:
    def frequencySort(self, s: str) -> str:
        count = Counter(s)
        buckets = [[] for _ in range(len(s) + 1)]
        for ch, freq in count.items():
            buckets[freq].append(ch)
        result = []
        for freq in range(len(buckets) - 1, 0, -1):
            for ch in buckets[freq]:
                result.append(ch * freq)
        return "".join(result)
Explanation:

  1. Place each character in bucket indexed by its frequency.
  2. Concatenate from highest bucket down — linear when freq ≤ n.

Time: O(n) · Space: O(n)

Problem 6: Reorganize String (Leetcode:767)#

Problem Statement

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" if not possible.

Example 1:

Input: s = "aab"
Output: "aba"

Example 2:

Input: s = "aaab"
Output: ""

Constraints:

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import heapq
from collections import Counter

class Solution:
    def reorganizeString(self, s: str) -> str:
        count = Counter(s)
        max_freq = max(count.values())
        if max_freq > (len(s) + 1) // 2:
            return ""

        heap = [(-freq, ch) for ch, freq in count.items()]
        heapq.heapify(heap)
        result = []
        prev = None  # (neg_freq, ch) waiting to re-enter heap

        while heap or prev:
            if prev and not heap:
                return ""  # cannot place prev without gap
            neg_freq, ch = heapq.heappop(heap)
            result.append(ch)
            if prev:
                heapq.heappush(heap, prev)
                prev = None
            if neg_freq + 1 < 0:  # still has copies left
                prev = (neg_freq + 1, ch)
        return "".join(result)
Explanation:

  1. Impossible check: most frequent char cannot exceed (n+1)//2 slots.
  2. Max-heap via (-freq, ch) — always place the most frequent available char.
  3. Hold one char in prev (cooldown of 1) so the same letter is never adjacent.

Time: O(n log m) · Space: O(m)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
from collections import Counter

class Solution:
    def reorganizeString(self, s: str) -> str:
        count = Counter(s)
        max_freq = max(count.values())
        if max_freq > (len(s) + 1) // 2:
            return ""
        chars = sorted(count.keys(), key=lambda c: -count[c])
        result = [""] * len(s)
        idx = 0
        for ch in chars:
            for _ in range(count[ch]):
                result[idx] = ch
                idx += 2
                if idx >= len(s):
                    idx = 1
        return "".join(result)
Explanation:

  1. Fill even indices (0, 2, 4, …) then odd indices — guarantees no adjacency when feasible.
  2. No heap; same feasibility check as Approach 1.

Time: O(n log m) · Space: O(n)

Problem 7: Rearrange String k Distance Apart (Leetcode:358)#

Problem Statement

Given a string s and an integer k, rearrange s such that the same characters are at least distance k from each other. If it is not possible to rearrange the string, return an empty string "".

Example 1:

Input: s = "aabbcc", k = 3
Output: "abcabc"
Explanation: The same letters are at least a distance of 3 from each other.

Example 2:

Input: s = "aaabc", k = 3
Output: ""
Explanation: It is not possible to rearrange the string.

Example 3:

Input: s = "aaadbbcc", k = 2
Output: "abacabcd"
Explanation: The same letters are at least a distance of 2 from each other.

Constraints:

  • 1 <= s.length <= 3 * 105
  • s consists of only lowercase English letters.
  • 0 <= k <= s.length
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
import heapq
from collections import Counter, deque

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        if k == 0:
            return s
        count = Counter(s)
        heap = [(-freq, ch) for ch, freq in count.items()]
        heapq.heapify(heap)
        result = []
        wait = deque()  # (neg_freq, ch, available_at_index)

        while heap:
            neg_freq, ch = heapq.heappop(heap)
            result.append(ch)
            if neg_freq + 1 < 0:
                wait.append((neg_freq + 1, ch, len(result) + k - 1))
            if wait and wait[0][2] == len(result):
                heapq.heappush(heap, wait.popleft()[:2])
        return "".join(result) if len(result) == len(s) else ""
Explanation:

  1. Generalization of LC 767: same char must be k positions apart.
  2. Max-heap picks most frequent; chars on cooldown sit in a queue until available_at_index.
  3. If result length < |s|, some char could not be placed in time → return "".

Time: O(n log m) · Space: O(m + k)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import heapq
from collections import Counter, deque

class Solution:
    def rearrangeString(self, s: str, k: int) -> str:
        if k <= 1:
            return s
        count = Counter(s)
        n = len(s)
        max_freq = max(count.values())
        # Not enough positions to separate the dominant char by k gaps
        if (max_freq - 1) * (k - 1) + max_freq > n:
            return ""
        # Same max-heap + cooldown queue as Approach 1
        heap = [(-freq, ch) for ch, freq in count.items()]
        heapq.heapify(heap)
        result, wait = [], deque()
        while heap:
            neg_freq, ch = heapq.heappop(heap)
            result.append(ch)
            if neg_freq + 1 < 0:
                wait.append((neg_freq + 1, ch, len(result) + k - 1))
            if wait and wait[0][2] == len(result):
                heapq.heappush(heap, wait.popleft()[:2])
        return "".join(result) if len(result) == n else ""
Explanation:

  1. Feasibility first: if the most frequent char needs more slots than exist with gap k, fail early.
  2. Construction is identical to Approach 1 — the heap pattern is the only practical builder for general k.
  3. Separating check from build clarifies why some inputs return "".

Time: O(n log m) · Space: O(m + k)

Problem 8: Minimum Cost to Connect Sticks (Leetcode:1167)#

Problem Statement

You have n sticks of the given lengths. Your task is to connect all the sticks into one stick. Find the minimum cost of connecting all the given sticks.

The cost of connecting two sticks is the sum of their lengths. After connecting two sticks, you get one stick whose length is the sum of both sticks' lengths.

Example 1:

Input: sticks = [2,4,3]
Output: 14
Explanation: Merge 2 + 3 = 5 (cost 5), then 4 + 5 = 9 (cost 9). Total = 14.

Example 2:

Input: sticks = [1,8,3,5]
Output: 30

Example 3:

Input: sticks = [5]
Output: 0

Constraints:

  • 1 <= sticks.length <= 104
  • 1 <= sticks[i] <= 104
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
import heapq

class Solution:
    def connectSticks(self, sticks: list[int]) -> int:
        heapq.heapify(sticks)
        cost = 0
        while len(sticks) > 1:
            a = heapq.heappop(sticks)
            b = heapq.heappop(sticks)
            merged = a + b
            cost += merged
            heapq.heappush(sticks, merged)
        return cost
Explanation:

  1. Always merge the two smallest sticks first — min-heap gives them in O(log n).
  2. Pay a + b each merge; push combined stick back.
  3. Same greedy structure as Huffman coding — smaller sticks participate in more merges, so merge them early.

Time: O(n log n) · Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def connectSticks(self, sticks: list[int]) -> int:
        sticks.sort()
        cost = 0
        while len(sticks) > 1:
            a = sticks.pop(0)
            b = sticks.pop(0)
            merged = a + b
            cost += merged
            sticks.append(merged)
            sticks.sort()
        return cost
Explanation:

  1. Same greedy logic but re-sort after each merge.
  2. Correct but O(n² log n) — illustrates why heap is preferred.

Time: O(n² log n) · Space: O(n)

Problem 9: Minimum Cost to Hire K Workers (Leetcode:857)#

Problem Statement

There are n workers. You are given two integer arrays quality and wage where quality[i] is the quality of the ith worker and wage[i] is the minimum wage expectation for the ith worker.

We want to hire exactly k workers to form a paid group. To hire a group of k workers, we must pay them according to the following rules:

  1. Every worker in the paid group must be paid at least their minimum wage expectation.
  2. In the group, each worker's pay must be directly proportional to their quality. This means if a worker’s quality is double that of another worker in the group, then they must be paid twice as much as the other worker.

Given the integer k, return the least amount of money needed to form a paid group satisfying the above conditions. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input: quality = [10,20,5], wage = [70,50,30], k = 2
Output: 105.00000
Explanation: We pay 70 to 0th worker and 35 to 2nd worker.

Example 2:

Input: quality = [3,1,10,10,1], wage = [4,8,2,2,7], k = 3
Output: 30.66667
Explanation: We pay 4 to 0th worker, 13.33333 to 2nd and 3rd workers separately.

Constraints:

  • n == quality.length == wage.length
  • 1 <= k <= n <= 104
  • 1 <= quality[i], wage[i] <= 104
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
import heapq

class Solution:
    def mincostToHireWorkers(self, quality: list[int], wage: list[int], k: int) -> float:
        workers = sorted((w / q, q, w) for q, w in zip(quality, wage))
        heap = []       # max-heap on quality via negation
        quality_sum = 0
        best = float("inf")

        for ratio, q, w in workers:
            heapq.heappush(heap, -q)
            quality_sum += q
            if len(heap) > k:
                quality_sum += heapq.heappop(heap)  # pop adds back negated q
            if len(heap) == k:
                # ratio is max wage/quality in group → total = ratio * sum(quality)
                best = min(best, ratio * quality_sum)
        return best
Explanation:

  1. Sort workers by wage/quality ratio — the captain (highest ratio) sets pay for the group.
  2. For each captain, keep k workers with smallest quality sum via max-heap on quality (-q).
  3. Total cost = captain_ratio × sum(qualities).

Time: O(n log n) · Space: O(k)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
from itertools import combinations

class Solution:
    def mincostToHireWorkers(self, quality: list[int], wage: list[int], k: int) -> float:
        n = len(quality)
        best = float("inf")
        for group in combinations(range(n), k):
            ratio = max(wage[i] / quality[i] for i in group)
            total_q = sum(quality[i] for i in group)
            best = min(best, ratio * total_q)
        return best
Explanation:

  1. Try every k-subset; compute required ratio and cost.
  2. O(C(n,k)) — only for understanding; heap + sort is the interview solution.

Time: O(C(n, k) · k) · Space: O(k)

Problem 10: Minimum Number of Refueling Stops (Leetcode:871)#

Problem Statement

A car travels from a starting position to a destination which is target miles east of the starting position.

There are gas stations along the way. The gas stations are represented as an array stations where stations[i] = [positioni, fueli] indicates that the ith gas station is positioni miles east of the starting position and has fueli liters of gas.

The car starts with an infinite tank of gas, which initially has startFuel liters of fuel in it. It uses one liter of gas per one mile that it drives. When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.

Return the minimum number of refueling stops the car must make in order to reach its destination. If it cannot reach the destination, return -1.

Note that if the car reaches a gas station with 0 fuel left, the car can still refuel there. If the car reaches the destination with 0 fuel left, it is still considered to have arrived.

Example 1:

Input: target = 1, startFuel = 1, stations = []
Output: 0
Explanation: We can reach the target without refueling.

Example 2:

Input: target = 100, startFuel = 1, stations = [[10,100]]
Output: -1
Explanation: We can not reach the target (or even the first gas station).

Example 3:

Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output: 2
Explanation: We start with 10 liters of fuel.
We drive to position 10, expending 10 liters of fuel. We refuel from 0 liters to 60 liters of gas.
Then, we drive from position 10 to position 60 (expending 50 liters of fuel),
and refuel from 10 liters to 50 liters of gas. We then drive to and reach the target.
We made 2 refueling stops along the way, so we return 2.

Constraints:

  • 1 <= target, startFuel <= 109
  • 0 <= stations.length <= 500
  • 1 <= positioni < positioni+1 < target
  • 1 <= fueli < 109
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
import heapq

class Solution:
    def minRefuelStops(self, target: int, startFuel: int,
                       stations: list[list[int]]) -> int:
        heap = []  # max-heap on fuel via negation
        fuel = startFuel
        stops = 0
        i = 0
        n = len(stations)

        while fuel < target:
            # Add every station we can reach into the heap
            while i < n and stations[i][0] <= fuel:
                heapq.heappush(heap, -stations[i][1])
                i += 1
            if not heap:
                return -1
            fuel += -heapq.heappop(heap)  # take largest fuel seen
            stops += 1
        return stops
Explanation:

  1. Drive as far as current fuel allows; push all reachable stations' fuel into a max-heap (-fuel).
  2. If you cannot reach target, retroactively refuel at the largest station passed (pop max).
  3. Greedy: using the biggest fuel tank among past options always maximizes future reach with fewest stops.

Time: O(n log n) · Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def minRefuelStops(self, target: int, startFuel: int,
                       stations: list[list[int]]) -> int:
        n = len(stations)
        dp = [0] * (n + 1)
        dp[0] = startFuel
        for i in range(n):
            for j in range(i, -1, -1):
                if dp[j] >= stations[i][0]:
                    dp[j + 1] = max(dp[j + 1], dp[j] + stations[i][1])
        for j in range(n + 1):
            if dp[j] >= target:
                return j
        return -1
Explanation:

  1. dp[j] = max fuel reachable with exactly j stops after processing stations.
  2. Not heap-based; useful when you need exact reachability table.
  3. Approach 1 is the standard heap-greedy solution.

Time: O(n²) · Space: O(n)

Problem 11: The K Weakest Rows in a Matrix (Leetcode:1337)#

Problem Statement

You are given an m x n binary matrix mat of 1's (representing soldiers) and 0's (representing civilians). The soldiers are positioned in front of the civilians. That is, all the 1's will appear to the left of all the 0's in each row.

A row i is weaker than a row j if one of the following is true:

  • The number of soldiers in row i is less than the number of soldiers in row j.
  • Both rows have the same number of soldiers and i < j.

Return the indices of the k weakest rows in the matrix ordered from weakest to strongest.

Example 1:

Input: mat =
[[1,1,0,0,0],
[1,1,1,1,0],
[1,0,0,0,0],
[1,1,0,0,0],
[1,1,1,1,1]],
k = 3
Output: [2,0,3]
Explanation:
The number of soldiers in each row is:
- Row 0: 2
- Row 1: 4
- Row 2: 1
- Row 3: 2
- Row 4: 5
The rows ordered from weakest to strongest are [2,0,3,1,4].

Example 2:

Input: mat =
[[1,0,0,0],
[1,1,1,1],
[1,0,0,0],
[1,0,0,0]],
k = 2
Output: [0,2]
Explanation:
The number of soldiers in each row is:
- Row 0: 1
- Row 1: 4
- Row 2: 1
- Row 3: 1
The rows ordered from weakest to strongest are [0,2,3,1].

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 2 <= n, m <= 100
  • 1 <= k <= m
  • matrix[i][j] is either 0 or 1.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import heapq

class Solution:
    def kWeakestRows(self, mat: list[list[int]], k: int) -> list[int]:
        def soldier_count(row):
            lo, hi = 0, len(row)
            while lo < hi:
                mid = (lo + hi) // 2
                if row[mid] == 1:
                    lo = mid + 1
                else:
                    hi = mid
            return lo

        heap = []
        counts = []
        for i, row in enumerate(mat):
            cnt = soldier_count(row)
            counts.append(cnt)
            heapq.heappush(heap, (-cnt, -i, i))
            if len(heap) > k:
                heapq.heappop(heap)
        return sorted([idx for _, _, idx in heap],
                      key=lambda i: (counts[i], i))
Explanation:

  1. Count soldiers per row with binary search (rows are sorted 1s then 0s).
  2. Use (-cnt, -i, row_index) as max-heap key — evict strongest (or higher index on tie).
  3. Sort remaining indices for output order weakest → stronger.

Time: O(m log n + m log k) · Space: O(k)

1
2
3
4
5
class Solution:
    def kWeakestRows(self, mat: list[list[int]], k: int) -> list[int]:
        def strength(i):
            return (sum(mat[i]), i)
        return [i for _, i in sorted(range(len(mat)), key=strength)[:k]]
Explanation:

  1. Sort row indices by (soldier_count, row_index).
  2. Simpler when m ≤ 100; heap wins when m is large and k is small.

Time: O(m log m) · Space: O(m)

Problem 12: Last Stone Weight (Leetcode:1046)#

Problem Statement

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

  • If x == y, both stones are destroyed, and
  • If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

At the end of the game, there is at most one stone left.

Return the weight of the last remaining stone. If there are no stones left, return 0.

Example 1:

Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation:
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.

Example 2:

Input: stones = [1]
Output: 1

Constraints:

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 1000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
import heapq

class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        heap = [-s for s in stones]
        heapq.heapify(heap)
        while len(heap) > 1:
            y = -heapq.heappop(heap)
            x = -heapq.heappop(heap)
            if y > x:
                heapq.heappush(heap, -(y - x))
        return -heap[0] if heap else 0
Explanation:

  1. Negate all weights → min-heap acts as max-heap.
  2. Pop two heaviest; if unequal push difference back.
  3. Direct simulation of the game — each smash is O(log n).

Time: O(n log n) · Space: O(n)

1
2
3
4
5
6
7
8
class Solution:
    def lastStoneWeight(self, stones: list[int]) -> int:
        while len(stones) > 1:
            stones.sort()
            y, x = stones.pop(), stones.pop()
            if y > x:
                stones.append(y - x)
        return stones[0] if stones else 0
Explanation:

  1. Sort and pop two largest each turn.
  2. O(n² log n) — fine for n ≤ 30 per constraints.

Time: O(n² log n) · Space: O(1)

Problem 13: Ugly Number II (Leetcode:264)#

Problem Statement

An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Given an integer n, return the nth ugly number.

Example 1:

Input: n = 10
Output: 12
Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.

Example 2:

Input: n = 1
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.

Constraints:

  • 1 <= n <= 1690
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
import heapq

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        heap = [1]
        seen = {1}
        for _ in range(n - 1):
            ugly = heapq.heappop(heap)
            for factor in (2, 3, 5):
                nxt = ugly * factor
                if nxt not in seen:
                    seen.add(nxt)
                    heapq.heappush(heap, nxt)
        return heap[0]
Explanation:

  1. Each ugly number spawns up to three streams (×2, ×3, ×5).
  2. Min-heap always yields the smallest unseen ugly number — classic merge k sorted streams.
  3. seen set avoids duplicate pushes (e.g. 2×3 = 3×2).

Time: O(n log n) · Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        ugly = [1]
        i2 = i3 = i5 = 0
        while len(ugly) < n:
            nxt = min(ugly[i2] * 2, ugly[i3] * 3, ugly[i5] * 5)
            ugly.append(nxt)
            if nxt == ugly[i2] * 2:
                i2 += 1
            if nxt == ugly[i3] * 3:
                i3 += 1
            if nxt == ugly[i5] * 5:
                i5 += 1
        return ugly[-1]
Explanation:

  1. Three pointers into the ugly list — each tracks the next multiple of 2, 3, or 5.
  2. O(n) time, no heap; same merge-stream idea without priority queue overhead.
  3. See also K-way Merge doc for the pointer variant at scale.

Time: O(n) · Space: O(n)

Two Heaps#

Maintain a max-heap for the lower half and a min-heap for the upper half. Balance sizes so len(low) >= len(high) and len(low) <= len(high) + 1. Median = top of max-heap (odd) or average of both tops (even).

Problem 1: Sliding Window Median (Leetcode:480)#

Problem Statement

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle values.

  • For examples, if arr = [2,3,4], the median is 3.
  • For examples, if arr = [1,2,3,4], the median is (2 + 3) / 2 = 2.5.

You are given an integer array nums and an integer k. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the median array for each window in the original array. Answers within 10-5 of the actual value will be accepted.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
Explanation:
Window position Median
--------------- -----
[1 3 -1] -3 5 3 6 7 1
1 [3 -1 -3] 5 3 6 7 -1
1 3 [-1 -3 5] 3 6 7 -1
1 3 -1 [-3 5 3] 6 7 3
1 3 -1 -3 [5 3 6] 7 5
1 3 -1 -3 5 [3 6 7] 6

Example 2:

Input: nums = [1,2,3,4,2,3,1,4,2], k = 3
Output: [2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]

Constraints:

  • 1 <= k <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import heapq
from collections import defaultdict

class Solution:
    def medianSlidingWindow(self, nums: list[int], k: int) -> list[float]:
        small, large = [], []       # max-heap (negated), min-heap
        delayed = defaultdict(int)
        small_size = large_size = 0

        def prune(heap, sign):
            while heap and delayed[sign * heap[0]]:
                delayed[sign * heap[0]] -= 1
                heapq.heappop(heap)

        def balance():
            nonlocal small_size, large_size
            if small_size > large_size + 1:
                heapq.heappush(large, -heapq.heappop(small))
                small_size -= 1
                large_size += 1
            elif large_size > small_size:
                heapq.heappush(small, -heapq.heappop(large))
                large_size -= 1
                small_size += 1

        def add(num):
            nonlocal small_size, large_size
            if not small or num <= -small[0]:
                heapq.heappush(small, -num)
                small_size += 1
            else:
                heapq.heappush(large, num)
                large_size += 1
            balance()

        def remove(num):
            nonlocal small_size, large_size
            delayed[num] += 1
            if num <= -small[0]:
                small_size -= 1
            else:
                large_size -= 1
            balance()

        def median():
            prune(small, -1)
            prune(large, 1)
            if k % 2:
                return float(-small[0])
            return (-small[0] + large[0]) / 2.0

        result = []
        for i, num in enumerate(nums):
            add(num)
            if i >= k:
                remove(nums[i - k])
            if i >= k - 1:
                result.append(median())
        return result
Explanation:

  1. Two heaps: small (max via negation) = lower half; large (min-heap) = upper half.
  2. Track logical sizes separately; lazy-delete removed values in delayed and prune stale tops.
  3. Median = root of max-heap (odd k) or average of both roots (even k).

Time: O(n log k) · Space: O(k)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
from sortedcontainers import SortedList

class Solution:
    def medianSlidingWindow(self, nums: list[int], k: int) -> list[float]:
        window = SortedList(nums[:k])
        result = []
        for i in range(k, len(nums) + 1):
            if k % 2:
                result.append(float(window[k // 2]))
            else:
                result.append((window[k // 2 - 1] + window[k // 2]) / 2)
            if i < len(nums):
                window.remove(nums[i - k])
                window.add(nums[i])
        return result
Explanation:

  1. Balanced BST / SortedList gives O(log k) add/remove with direct median access.
  2. Simpler logic; requires external library. Two-heap + lazy delete is the stdlib heap pattern.

Time: O(n log k) · Space: O(k)

Problem 2: Find Median from Data Stream (Leetcode:295)#

Problem Statement

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

  • For example, for arr = [2,3,4], the median is 3.
  • For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

  • MedianFinder() initializes the MedianFinder object.
  • void addNum(int num) adds the integer num from the data stream to the data structure.
  • double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

Constraints:

  • -105 <= num <= 105
  • There will be at least one element in the data structure before calling findMedian.
  • At most 5 * 104 calls will be made to addNum and findMedian.

Follow up:

  • If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
  • If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
import heapq

class MedianFinder:
    def __init__(self):
        self.small = []  # max-heap (negated values)
        self.large = []  # min-heap

    def addNum(self, num: int) -> None:
        heapq.heappush(self.small, -num)
        heapq.heappush(self.large, -heapq.heappop(self.small))
        if len(self.large) > len(self.small):
            heapq.heappush(self.small, -heapq.heappop(self.large))

    def findMedian(self) -> float:
        if len(self.small) > len(self.large):
            return float(-self.small[0])
        return (-self.small[0] + self.large[0]) / 2.0
Explanation:

  1. Every addNum goes to small first, then the largest of small moves to large.
  2. Rebalance: if large is bigger, move its minimum back to small.
  3. Invariant: len(small) >= len(large) and differ by at most 1 → median at heap tops. No lazy delete needed (only inserts).

Time: O(log n) per add · Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
import bisect

class MedianFinder:
    def __init__(self):
        self.nums = []

    def addNum(self, num: int) -> None:
        bisect.insort(self.nums, num)

    def findMedian(self) -> float:
        n = len(self.nums)
        if n % 2:
            return float(self.nums[n // 2])
        return (self.nums[n // 2 - 1] + self.nums[n // 2]) / 2.0
Explanation:

  1. Keep a sorted array via bisect.insort — O(n) per insert due to shifting.
  2. Two-heap is strictly better at O(log n) per insert for large streams.

Time: O(n) per add · Space: O(n)

Problem 3: IPO / Maximize Capital (Leetcode:502)#

Problem Statement

Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given n projects where the ith project has a pure profit profits[i] and a minimum capital of capital[i] is needed to start it.

Initially, you have w capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital.

Pick a list of at most k distinct projects from given projects to maximize your final capital, and return the final maximized capital.

The answer is guaranteed to fit in a 32-bit signed integer.

Example 1:

Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
Explanation: Since your initial capital is 0, you can only start the project indexed 0.
After finishing it you will obtain profit 1 and your capital becomes 1.
With capital 1, you can either start the project indexed 1 or the project indexed 2.
Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital.
Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.

Example 2:

Input: k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
Output: 6

Constraints:

  • 1 <= k <= 105
  • 0 <= w <= 109
  • n == profits.length
  • n == capital.length
  • 1 <= n <= 105
  • 0 <= profits[i] <= 104
  • 0 <= capital[i] <= 109
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
import heapq

class Solution:
    def findMaximizedCapital(self, k: int, w: int,
                             profits: list[int], capital: list[int]) -> int:
        projects = sorted(zip(capital, profits))
        affordable = []  # max-heap on profit via -profit
        i = 0
        n = len(projects)

        for _ in range(k):
            while i < n and projects[i][0] <= w:
                heapq.heappush(affordable, -projects[i][1])
                i += 1
            if not affordable:
                break
            w += -heapq.heappop(affordable)
        return w
Explanation:

  1. Sort projects by minimum capital required.
  2. Push all affordable projects' profits into a max-heap (-profit).
  3. Each round: pick highest profit among affordable projects, add to capital, unlock more projects.
  4. Two-heap flavor: one sorted stream + one profit heap.

Time: O(n log n) · Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def findMaximizedCapital(self, k: int, w: int,
                             profits: list[int], capital: list[int]) -> int:
        done = [False] * len(profits)
        for _ in range(k):
            best_profit, best_j = -1, -1
            for j in range(len(profits)):
                if not done[j] and capital[j] <= w and profits[j] > best_profit:
                    best_profit, best_j = profits[j], j
            if best_j == -1:
                break
            done[best_j] = True
            w += best_profit
        return w
Explanation:

  1. Linear scan for best affordable project each of k rounds.
  2. O(nk) — heap version avoids repeated scans.

Time: O(nk) · Space: O(n)

Problem 4: Kth Largest Element in a Stream (Leetcode:703)#

Problem Statement

You are part of a university admissions office and need to keep track of the kth highest test score from applicants in real-time. This helps to determine cut-off marks for interviews and admissions dynamically as new applicants submit their scores.

You are tasked to implement a class which, for a given integer k, maintains a stream of test scores and continuously returns the kth highest test score after a new score has been submitted. More specifically, we are looking for the kth highest score in the sorted list of all scores.

Implement the KthLargest class:

  • KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of test scores nums.
  • int add(int val) Adds a new test score val to the stream and returns the element representing the kth largest element in the pool of test scores so far.

Example 1:

Input:
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
Output: [null, 4, 5, 5, 8, 8]
Explanation:
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3); // return 4
kthLargest.add(5); // return 5
kthLargest.add(10); // return 5
kthLargest.add(9); // return 8
kthLargest.add(4); // return 8

Example 2:

Input:
["KthLargest", "add", "add", "add", "add"]
[[4, [7, 7, 7, 7, 8, 3]], [2], [10], [9], [9]]
Output: [null, 7, 7, 7, 8]
Explanation:
KthLargest kthLargest = new KthLargest(4, [7, 7, 7, 7, 8, 3]);
kthLargest.add(2); // return 7
kthLargest.add(10); // return 7
kthLargest.add(9); // return 7
kthLargest.add(9); // return 8

Constraints:

  • 0 <= nums.length <= 104
  • 1 <= k <= nums.length + 1
  • -104 <= nums[i] <= 104
  • -104 <= val <= 104
  • At most 104 calls will be made to add.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
import heapq

class KthLargest:
    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.heap = nums
        heapq.heapify(self.heap)
        while len(self.heap) > k:
            heapq.heappop(self.heap)

    def add(self, val: int) -> int:
        heapq.heappush(self.heap, val)
        if len(self.heap) > self.k:
            heapq.heappop(self.heap)
        return self.heap[0]
Explanation:

  1. Maintain min-heap of size k — root is always the kth largest in the stream.
  2. On each add, push and evict smallest if over capacity.
  3. Same top-k trick as LC 215, adapted for streaming.

Time: O(log k) per add · Space: O(k)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
import bisect

class KthLargest:
    def __init__(self, k: int, nums: list[int]):
        self.k = k
        self.nums = sorted(nums)

    def add(self, val: int) -> int:
        bisect.insort(self.nums, val)
        return self.nums[-self.k]
Explanation:

  1. Keep full sorted list; kth largest = nums[-k].
  2. O(n) insert — only viable for tiny streams.

Time: O(n) per add · Space: O(n)

Scheduling Pattern#

Use heaps when the next decision depends on earliest finish time, highest priority task, or best available resource.

Problem 1: Meeting Rooms II (Leetcode:253)#

Problem Statement

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: 1

Constraints:

  • 1 <= intervals.length <= 104
  • 0 <= starti < endi <= 106
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
import heapq

class Solution:
    def minMeetingRooms(self, intervals: list[list[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort(key=lambda x: x[0])
        heap = []  # end times of ongoing meetings
        for start, end in intervals:
            if heap and heap[0] <= start:
                heapq.heappop(heap)  # reuse room that freed earliest
            heapq.heappush(heap, end)
        return len(heap)
Explanation:

  1. Sort by start time. For each meeting, check if earliest-ending room is free (heap[0] <= start).
  2. Min-heap tracks end times — root = room available soonest.
  3. Heap size = concurrent meetings = minimum rooms needed.

Time: O(n log n) · Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def minMeetingRooms(self, intervals: list[list[int]]) -> int:
        starts = sorted(s for s, _ in intervals)
        ends = sorted(e for _, e in intervals)
        rooms = max_rooms = 0
        i = j = 0
        while i < len(starts):
            if starts[i] < ends[j]:
                rooms += 1
                max_rooms = max(max_rooms, rooms)
                i += 1
            else:
                rooms -= 1
                j += 1
        return max_rooms
Explanation:

  1. Two pointers on sorted starts and ends — increment rooms on start, decrement on end.
  2. Track peak concurrent count. No heap; same O(n log n) from sorting.

Time: O(n log n) · Space: O(n)

Problem 2: Employee Free Time (Leetcode:759)#

Problem Statement

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined. Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.)

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation: There are a total of three employees, and all common free time intervals would be [-inf, 1], [3, 4], [10, inf]. We discard any intervals that contain inf as they aren't finite.

Example 2:

Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]

Constraints:

  • 1 <= schedule.length , schedule[i].length <= 50
  • 0 <= schedule[i].start < schedule[i].end <= 108
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import heapq

class Interval:
    def __init__(self, start=0, end=0):
        self.start = start
        self.end = end

class Solution:
    def employeeFreeTime(self, schedule: list[list[Interval]]) -> list[Interval]:
        heap = []
        for i, emp in enumerate(schedule):
            if emp:
                heapq.heappush(heap, (emp[0].start, i, 0))

        result = []
        prev_end = heap[0][0] if heap else 0

        while heap:
            start, i, j = heapq.heappop(heap)
            if start > prev_end:
                result.append(Interval(prev_end, start))
            prev_end = max(prev_end, schedule[i][j].end)
            if j + 1 < len(schedule[i]):
                heapq.heappush(heap, (schedule[i][j + 1].start, i, j + 1))
        return result
Explanation:

  1. Each employee's busy intervals form a sorted stream; seed a min-heap with each employee's first interval.
  2. Pop earliest-starting interval globally; gap between prev_end and next start is shared free time.
  3. Classic merge k sorted streams pattern.

Time: O(N log k) · Space: O(k)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Interval:
    def __init__(self, start=0, end=0):
        self.start = start
        self.end = end

class Solution:
    def employeeFreeTime(self, schedule: list[list[Interval]]) -> list[Interval]:
        all_busy = []
        for emp in schedule:
            all_busy.extend(emp)
        all_busy.sort(key=lambda x: x.start)

        merged = []
        for iv in all_busy:
            if not merged or iv.start > merged[-1].end:
                merged.append(Interval(iv.start, iv.end))
            else:
                merged[-1].end = max(merged[-1].end, iv.end)

        result = []
        for i in range(1, len(merged)):
            if merged[i].start > merged[i - 1].end:
                result.append(Interval(merged[i - 1].end, merged[i].start))
        return result
Explanation:

  1. Collect all intervals, sort, merge overlaps, report gaps.
  2. O(N log N) — simpler; heap wins when streams are already per-employee sorted.

Time: O(N log N) · Space: O(N)

Problem 3: Task Scheduler (Leetcode:621)#

Problem Statement

You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there's a constraint: there has to be a gap of at least n intervals between two tasks with the same label.

Return the minimum number of CPU intervals required to complete all tasks.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B.
After completing task A, you must wait two intervals before doing A again. The same applies to task B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th interval, you can do A again as 2 intervals have passed.

Example 2:

Input: tasks = ["A","C","A","B","D","B"], n = 1
Output: 6
Explanation: A possible sequence is: A -> B -> C -> D -> A -> B. With a cooling interval of 1, you can repeat a task after just one other task.

Example 3:

Input: tasks = ["A","A","A", "B","B","B"], n = 3
Output: 10
Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B. There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.

Constraints:

  • 1 <= tasks.length <= 104
  • tasks[i] is an uppercase English letter.
  • 0 <= n <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
import heapq
from collections import Counter, deque

class Solution:
    def leastInterval(self, tasks: list[str], n: int) -> int:
        count = Counter(tasks)
        heap = [-c for c in count.values()]
        heapq.heapify(heap)
        time = 0
        wait = deque()  # (neg_count, available_at)

        while heap or wait:
            time += 1
            if heap:
                cnt = heapq.heappop(heap) + 1
                if cnt:
                    wait.append((cnt, time + n))
            if wait and wait[0][1] == time:
                heapq.heappush(heap, wait.popleft()[0])
        return time
Explanation:

  1. Max-heap on task counts (-count) — always schedule the most frequent remaining task.
  2. After scheduling, task sits in cooldown queue for n slots (same pattern as reorganize string).
  3. Time advances each tick; idle slots fill automatically when heap empty but cooldown pending.

Time: O(m log m) · Space: O(m)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
from collections import Counter

class Solution:
    def leastInterval(self, tasks: list[str], n: int) -> int:
        count = Counter(tasks)
        max_freq = max(count.values())
        max_count = sum(1 for f in count.values() if f == max_freq)
        part_count = max_freq - 1
        part_length = n + 1
        min_slots = part_count * part_length + max_count
        return max(len(tasks), min_slots)
Explanation:

  1. Arrange most frequent task as skeleton with n gaps between repeats.
  2. min_slots = mandatory frame size; answer is max of that and len(tasks).
  3. No heap — faster O(m); heap approach generalizes when tie-breaking rules differ.

Time: O(m) · Space: O(1)

Problem 4: Furthest Building You Can Reach (Leetcode:1642)#

Problem Statement

You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.

You start your journey from building 0 and move to the next building by possibly using bricks or ladders.

While moving from building i to building i+1 (0-indexed),

  • If the current building's height is greater than or equal to the next building's height, you do not need a ladder or bricks.
  • If the current building's height is less than the next building's height, you can either use one ladder or (h[i+1] - h[i]) bricks.

Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.

Example 1:


Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Explanation: Starting at building 0, you can follow these steps:
- Go to building 1 without using ladders nor bricks since 4 >= 2.
- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7.
- Go to building 3 without using ladders nor bricks since 7 >= 6.
- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9.
It is impossible to go beyond building 4 because you do not have any more bricks or ladders.

Example 2:

Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7

Example 3:

Input: heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3

Constraints:

  • 1 <= heights.length <= 105
  • 1 <= heights[i] <= 106
  • 0 <= bricks <= 109
  • 0 <= ladders <= heights.length
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
import heapq

class Solution:
    def furthestBuilding(self, heights: list[int], bricks: int,
                         ladders: int) -> int:
        heap = []  # min-heap of climbs where we used a ladder
        for i in range(len(heights) - 1):
            climb = heights[i + 1] - heights[i]
            if climb <= 0:
                continue
            heapq.heappush(heap, climb)
            if len(heap) > ladders:
                bricks -= heapq.heappop(heap)  # replace smallest ladder use with bricks
            if bricks < 0:
                return i
        return len(heights) - 1
Explanation:

  1. Greedily use a ladder for every upward climb; track those climbs in a min-heap.
  2. When ladders exhausted, swap the cheapest ladder climb to bricks (pop smallest from heap).
  3. Min-heap keeps the ladders largest climbs on ladders — optimal resource allocation.

Time: O(n log ladders) · Space: O(ladders)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def furthestBuilding(self, heights: list[int], bricks: int,
                         ladders: int) -> int:
        climbs = []
        for i in range(len(heights) - 1):
            diff = heights[i + 1] - heights[i]
            if diff <= 0:
                continue
            climbs.append(diff)
            climbs.sort()
            if len(climbs) > ladders:
                bricks -= climbs.pop(0)
            if bricks < 0:
                return i
        return len(heights) - 1
Explanation:

  1. Same ladder/brick swap logic but re-sort after each climb.
  2. O(n²) — heap avoids repeated sorting.

Time: O(n²) · Space: O(n)

Problem 5: Course Schedule III (Leetcode:630)#

Problem Statement

There are n different online courses numbered from 1 to n. You are given an array courses where courses[i] = [durationi, lastDayi] indicate that the ith course should be taken continuously for durationi days and must be finished before or on lastDayi.

You will start on the 1st day and you cannot take two or more courses simultaneously.

Return the maximum number of courses that you can take.

Example 1:

Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]
Output: 3
Explanation:
There are totally 4 courses, but you can take 3 courses at most:
First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day.
Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day.
The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.

Example 2:

Input: courses = [[1,2]]
Output: 1

Example 3:

Input: courses = [[3,2],[4,3]]
Output: 0

Constraints:

  • 1 <= courses.length <= 104
  • 1 <= durationi, lastDayi <= 104
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
import heapq

class Solution:
    def scheduleCourse(self, courses: list[list[int]]) -> int:
        courses.sort(key=lambda x: x[1])  # sort by lastDay (deadline)
        heap = []  # max-heap on duration via negation
        time = 0
        for duration, last_day in courses:
            heapq.heappush(heap, -duration)
            time += duration
            if time > last_day:
                time += heapq.heappop(heap)  # drop longest course
        return len(heap)
Explanation:

  1. Sort by deadline (Earliest Deadline First).
  2. Greedily take each course; if total time exceeds deadline, drop the longest course taken so far (max-heap).
  3. Max-heap lets you undo the costliest choice — maximize count of feasible courses.

Time: O(n log n) · Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def scheduleCourse(self, courses: list[list[int]]) -> int:
        courses.sort(key=lambda x: x[1])
        best = 0

        def dfs(i, time, count):
            nonlocal best
            if i == len(courses):
                best = max(best, count)
                return
            d, last = courses[i]
            if time + d <= last:
                dfs(i + 1, time + d, count + 1)
            dfs(i + 1, time, count)

        dfs(0, 0, 0)
        return best
Explanation:

  1. Backtracking over sorted courses — exponential.
  2. Illustrates the greedy invariant; heap solution is required for n up to 10⁴.

Time: O(2^n) · Space: O(n)