1. Kth Largest Element In a Stream
Easy · LC 703
Design a class that accepts streaming integers and after each add call returns the kth largest value seen so far. Maintain a min-heap holding only the k largest elements: push every new value, then pop whenever the size exceeds k. The invariant is that the heap root is always the kth largest, so each add costs O(log k) and the smaller values are safely discarded.
class KthLargest:
"""LC 703. Kth Largest Element in a Stream.
Min-heap capped at k: push every new value and pop whenever the
size exceeds k, so the heap holds exactly the k largest seen and
its root is always the kth largest. Values smaller than the root
can never become the answer, which is why discarding them is safe.
O(log k) per add, O(k) space.
"""
def __init__(self, k: int, nums: list[int]) -> None:
self._k = k
self._top_k = list(nums)
heapq.heapify(self._top_k)
while len(self._top_k) > k:
heapq.heappop(self._top_k)
def add(self, val: int) -> int:
heapq.heappush(self._top_k, val)
if len(self._top_k) > self._k:
heapq.heappop(self._top_k)
return self._top_k[0]
// LC 703. Min-heap holding only the k largest values seen so far: push every
// newcomer, pop whenever the size exceeds k. The root is then always the kth
// largest, so each add costs O(log k).
class KthLargest {
int k;
priority_queue<int, vector<int>, greater<int>> largestK; // min-heap of the k largest
public:
KthLargest(int k, vector<int> nums) : k(k) {
for (int num : nums) add(num);
}
int add(int val) {
largestK.push(val);
if (static_cast<int>(largestK.size()) > k) largestK.pop();
return largestK.top();
}
};
/// LC 703. Min-heap (BinaryHeap of Reverse) holding only the k largest
/// values seen so far: push every newcomer, pop whenever the size exceeds
/// k. The invariant makes the root the kth largest at all times, so each
/// add is O(log k) and smaller values are discarded for free.
pub struct KthLargest {
k: usize,
top_k: BinaryHeap<Reverse<i32>>,
}
impl KthLargest {
pub fn new(k: i32, nums: Vec<i32>) -> Self {
let mut kth = KthLargest { k: k as usize, top_k: BinaryHeap::new() };
for num in nums {
kth.add(num);
}
kth
}
pub fn add(&mut self, val: i32) -> i32 {
self.top_k.push(Reverse(val));
if self.top_k.len() > self.k {
self.top_k.pop(); // evict the smallest; only the k largest stay
}
self.top_k.peek().unwrap().0
}
}
/** LC 703. Min-heap holding only the k largest seen; after trimming, the root is the kth largest. */
export class KthLargest {
private heap: number[] = []; // min-heap: the k largest values seen so far
private k: number;
constructor(k: number, nums: number[]) {
this.k = k;
for (const num of nums) this.add(num);
}
add(val: number): number {
this.push(val);
if (this.heap.length > this.k) this.pop(); // anything smaller can never be the kth largest
return this.heap[0];
}
private push(val: number): void {
const heap = this.heap;
heap.push(val);
let child = heap.length - 1;
while (child > 0) {
const parent = (child - 1) >> 1;
if (heap[parent] <= heap[child]) break;
[heap[parent], heap[child]] = [heap[child], heap[parent]];
child = parent;
}
}
private pop(): void {
const heap = this.heap;
const last = heap.pop()!;
if (heap.length === 0) return;
heap[0] = last;
let parent = 0;
for (;;) {
let smallest = parent;
const left = 2 * parent + 1;
const right = 2 * parent + 2;
if (left < heap.length && heap[left] < heap[smallest]) smallest = left;
if (right < heap.length && heap[right] < heap[smallest]) smallest = right;
if (smallest === parent) break;
[heap[parent], heap[smallest]] = [heap[smallest], heap[parent]];
parent = smallest;
}
}
}
// LC 703. Min-heap capped at k holds exactly the k largest values seen, so
// its root is always the kth largest; values below the root never matter.
type KthLargest struct {
k int
largest []int // min-heap of the k largest values
}
func newKthLargest(k int, nums []int) *KthLargest {
kth := &KthLargest{k: k}
for _, num := range nums {
kth.add(num)
}
return kth
}
func (kth *KthLargest) add(val int) int {
h := kth.largest
h = append(h, val)
for i := len(h) - 1; i > 0; {
parent := (i - 1) / 2
if h[parent] <= h[i] {
break
}
h[i], h[parent] = h[parent], h[i]
i = parent
}
if len(h) > kth.k { // pop the root: too small to ever be the answer
last := len(h) - 1
h[0] = h[last]
h = h[:last]
for i := 0; ; {
next := i
if l := 2*i + 1; l < len(h) && h[l] < h[next] {
next = l
}
if r := 2*i + 2; r < len(h) && h[r] < h[next] {
next = r
}
if next == i {
break
}
h[i], h[next] = h[next], h[i]
i = next
}
}
kth.largest = h
return h[0]
}
// LC 703. Min-heap holding only the k largest values seen so far: push every
// newcomer, pop past size k, and the root is always the kth largest.
class KthLargest {
private let k: Int
private var heap: [Int] = [] // min-heap of the k largest
init(_ k: Int, _ nums: [Int]) {
self.k = k
for num in nums { _ = add(num) }
}
func add(_ val: Int) -> Int {
push(val)
if heap.count > k { _ = pop() }
return heap[0]
}
private func push(_ val: Int) {
heap.append(val)
var child = heap.count - 1
while child > 0 {
let parent = (child - 1) / 2
if heap[parent] <= heap[child] { break }
heap.swapAt(parent, child)
child = parent
}
}
private func pop() -> Int {
let top = heap[0]
heap[0] = heap[heap.count - 1]
heap.removeLast()
var parent = 0
while true {
var smallest = parent
let left = 2 * parent + 1
let right = 2 * parent + 2
if left < heap.count && heap[left] < heap[smallest] { smallest = left }
if right < heap.count && heap[right] < heap[smallest] { smallest = right }
if smallest == parent { break }
heap.swapAt(parent, smallest)
parent = smallest
}
return top
}
}
2. Last Stone Weight
Easy · LC 1046
Given an array of stone weights, repeatedly smash the two heaviest stones, leaving their difference if unequal, and return the last remaining weight or zero. Use a max-heap: pop the two largest, push back the difference when it is nonzero, and loop until at most one stone remains. In Python, negate values to simulate a max-heap with heapq, and remember the empty-heap case returns zero.
def last_stone_weight(stones: list[int]) -> int:
"""LC 1046. Last Stone Weight.
Repeatedly smash the two heaviest stones. heapq is a min-heap, so
negate every weight to simulate a max-heap: pop the two largest,
push back the difference when nonzero, and stop when at most one
stone remains. O(n log n) time, O(n) space.
"""
negated: list[int] = [-stone for stone in stones]
heapq.heapify(negated)
while len(negated) > 1:
heaviest = -heapq.heappop(negated)
second = -heapq.heappop(negated)
if heaviest != second:
heapq.heappush(negated, -(heaviest - second))
return -negated[0] if negated else 0 # all stones may destroy each other
// LC 1046. Max-heap of weights: pop the two heaviest, push back the
// difference when nonzero, and loop until at most one stone remains.
// An empty heap at the end means everything annihilated, so return 0.
int lastStoneWeight(vector<int> stones) {
priority_queue<int> heap(stones.begin(), stones.end());
while (heap.size() > 1) {
int heaviest = heap.top();
heap.pop();
int second = heap.top();
heap.pop();
if (heaviest != second) heap.push(heaviest - second);
}
return heap.empty() ? 0 : heap.top();
}
/// LC 1046. Max-heap of weights: pop the two heaviest, push back the
/// difference when nonzero, and loop until at most one stone remains.
/// BinaryHeap is already a max-heap, so no negation trick is needed;
/// an empty heap at the end means every stone was destroyed, answer 0.
pub fn last_stone_weight(stones: Vec<i32>) -> i32 {
let mut heap: BinaryHeap<i32> = stones.into_iter().collect();
while heap.len() > 1 {
let heavier = heap.pop().unwrap();
let lighter = heap.pop().unwrap();
if heavier > lighter {
heap.push(heavier - lighter);
}
}
heap.pop().unwrap_or(0)
}
/** LC 1046. Max-heap: pop the two heaviest, push back the difference when nonzero, loop to one stone. */
export function lastStoneWeight(stones: number[]): number {
const heap: number[] = []; // max-heap of stone weights
const push = (val: number): void => {
heap.push(val);
let child = heap.length - 1;
while (child > 0) {
const parent = (child - 1) >> 1;
if (heap[parent] >= heap[child]) break;
[heap[parent], heap[child]] = [heap[child], heap[parent]];
child = parent;
}
};
const pop = (): number => {
const top = heap[0];
const last = heap.pop()!;
if (heap.length > 0) {
heap[0] = last;
let parent = 0;
for (;;) {
let largest = parent;
const left = 2 * parent + 1;
const right = 2 * parent + 2;
if (left < heap.length && heap[left] > heap[largest]) largest = left;
if (right < heap.length && heap[right] > heap[largest]) largest = right;
if (largest === parent) break;
[heap[parent], heap[largest]] = [heap[largest], heap[parent]];
parent = largest;
}
}
return top;
};
for (const stone of stones) push(stone);
while (heap.length > 1) {
const heaviest = pop();
const second = pop();
if (heaviest > second) push(heaviest - second); // equal stones annihilate, nothing returns
}
return heap.length === 0 ? 0 : heap[0];
}
// LC 1046. Greatest two stones smash; max-heap, push back the difference
// when nonzero, and an empty heap at the end means total annihilation.
func lastStoneWeight(stones []int) int {
heap := []int{}
push := func(v int) {
heap = append(heap, v)
for i := len(heap) - 1; i > 0; {
parent := (i - 1) / 2
if heap[parent] >= heap[i] {
break
}
heap[i], heap[parent] = heap[parent], heap[i]
i = parent
}
}
pop := func() int {
top := heap[0]
last := len(heap) - 1
heap[0] = heap[last]
heap = heap[:last]
for i := 0; ; {
next := i
if l := 2*i + 1; l < len(heap) && heap[l] > heap[next] {
next = l
}
if r := 2*i + 2; r < len(heap) && heap[r] > heap[next] {
next = r
}
if next == i {
break
}
heap[i], heap[next] = heap[next], heap[i]
i = next
}
return top
}
for _, stone := range stones {
push(stone)
}
for len(heap) > 1 {
heaviest, second := pop(), pop()
if heaviest != second {
push(heaviest - second)
}
}
if len(heap) == 0 {
return 0
}
return heap[0]
}
// LC 1046. Greatest two stones smash; push back the difference when nonzero
// (max-heap) and loop until at most one stone remains.
func lastStoneWeight(_ stones: [Int]) -> Int {
var heap: [Int] = [] // max-heap of stone weights
func push(_ val: Int) {
heap.append(val)
var child = heap.count - 1
while child > 0 {
let parent = (child - 1) / 2
if heap[parent] >= heap[child] { break }
heap.swapAt(parent, child)
child = parent
}
}
func pop() -> Int {
let top = heap[0]
heap[0] = heap[heap.count - 1]
heap.removeLast()
var parent = 0
while true {
var largest = parent
let left = 2 * parent + 1
let right = 2 * parent + 2
if left < heap.count && heap[left] > heap[largest] { largest = left }
if right < heap.count && heap[right] > heap[largest] { largest = right }
if largest == parent { break }
heap.swapAt(parent, largest)
parent = largest
}
return top
}
for stone in stones { push(stone) }
while heap.count > 1 {
let heaviest = pop()
let second = pop()
if heaviest != second { push(heaviest - second) }
}
return heap.isEmpty ? 0 : heap[0]
}
3. K Closest Points to Origin
Medium · LC 973
Given a list of 2D points and an integer k, return the k points closest to the origin by Euclidean distance, in any order. Keep a max-heap of size k keyed on squared distance, popping the farthest whenever the heap grows past k, for O(n log k). Compare squared distances to avoid floating-point square roots, and recall that quickselect achieves average O(n) when needed.
def k_closest(points: list[list[int]], k: int) -> list[list[int]]:
"""LC 973. K Closest Points to Origin.
Keep a max-heap of size k keyed on negated squared distance; once
the heap grows past k, the pop evicts the farthest point kept so
far. Squared distance preserves the ordering, so sqrt would only
add floating-point error. O(n log k) time, O(k) space.
"""
farthest_on_top: list[tuple[int, list[int]]] = []
for x, y in points:
heapq.heappush(farthest_on_top, (-(x * x + y * y), [x, y]))
if len(farthest_on_top) > k:
heapq.heappop(farthest_on_top) # the negated root is the farthest kept
return [point for _, point in farthest_on_top]
// LC 973. Size-k max-heap keyed on squared distance (no square roots needed):
// once the heap grows past k, the farthest point falls out, leaving the k
// closest in O(n log k). Drained back-to-front, the result is sorted by
// increasing distance.
vector<vector<int>> kClosest(vector<vector<int>> points, int k) {
priority_queue<pair<long long, vector<int>>> farthestFirst; // (squared distance, point)
for (vector<int>& point : points) {
long long squared = static_cast<long long>(point[0]) * point[0] +
static_cast<long long>(point[1]) * point[1];
farthestFirst.push({squared, point});
if (static_cast<int>(farthestFirst.size()) > k) farthestFirst.pop(); // farthest falls out
}
vector<vector<int>> closest(farthestFirst.size());
for (int i = static_cast<int>(closest.size()) - 1; i >= 0; --i) {
closest[i] = farthestFirst.top().second;
farthestFirst.pop();
}
return closest;
}
/// LC 973. Size-k MAX-heap keyed on squared distance: push every point and
/// pop the farthest whenever the heap grows past k, so only the k closest
/// survive -- O(n log k). Squared distance avoids floating-point sqrt and
/// orders identically.
pub fn k_closest(points: Vec<Vec<i32>>, k: i32) -> Vec<Vec<i32>> {
let mut farthest_out: BinaryHeap<(i64, i32, i32)> = BinaryHeap::new();
for point in &points {
let (x, y) = (point[0], point[1]);
let dist = (x as i64) * (x as i64) + (y as i64) * (y as i64);
farthest_out.push((dist, x, y));
if farthest_out.len() > k as usize {
farthest_out.pop(); // the current farthest can never be an answer
}
}
farthest_out.into_iter().map(|(_, x, y)| vec![x, y]).collect()
}
/** LC 973. Size-k max-heap on squared distance: pop the farthest past k; sqrt-free, O(n log k). */
export function kClosest(points: number[][], k: number): number[][] {
const squared = (p: number[]): number => p[0] * p[0] + p[1] * p[1];
const heap: number[][] = []; // max-heap by squared distance: the root is the farthest point kept
const push = (point: number[]): void => {
heap.push(point);
let child = heap.length - 1;
while (child > 0) {
const parent = (child - 1) >> 1;
if (squared(heap[parent]) >= squared(heap[child])) break;
[heap[parent], heap[child]] = [heap[child], heap[parent]];
child = parent;
}
};
const pop = (): void => {
const last = heap.pop()!;
if (heap.length === 0) return;
heap[0] = last;
let parent = 0;
for (;;) {
let farthest = parent;
const left = 2 * parent + 1;
const right = 2 * parent + 2;
if (left < heap.length && squared(heap[left]) > squared(heap[farthest])) farthest = left;
if (right < heap.length && squared(heap[right]) > squared(heap[farthest])) farthest = right;
if (farthest === parent) break;
[heap[parent], heap[farthest]] = [heap[farthest], heap[parent]];
parent = farthest;
}
};
for (const point of points) {
push(point);
if (heap.length > k) pop(); // the farthest of k + 1 points can never be in the answer
}
return heap;
}
// LC 973. Size-k max-heap on squared distance evicts the farthest point;
// drained back-to-front the survivors come out sorted by increasing distance.
func kClosest(points [][]int, k int) [][]int {
type entry struct {
dist int
point []int
}
heap := []entry{}
push := func(e entry) {
heap = append(heap, e)
for i := len(heap) - 1; i > 0; {
parent := (i - 1) / 2
if heap[parent].dist >= heap[i].dist {
break
}
heap[i], heap[parent] = heap[parent], heap[i]
i = parent
}
}
pop := func() entry {
top := heap[0]
last := len(heap) - 1
heap[0] = heap[last]
heap = heap[:last]
for i := 0; ; {
next := i
if l := 2*i + 1; l < len(heap) && heap[l].dist > heap[next].dist {
next = l
}
if r := 2*i + 2; r < len(heap) && heap[r].dist > heap[next].dist {
next = r
}
if next == i {
break
}
heap[i], heap[next] = heap[next], heap[i]
i = next
}
return top
}
for _, point := range points {
push(entry{point[0]*point[0] + point[1]*point[1], point})
if len(heap) > k {
pop() // the farthest point kept so far falls out
}
}
closest := make([][]int, len(heap))
for i := len(closest) - 1; i >= 0; i-- {
closest[i] = pop().point
}
return closest
}
// LC 973. Size-k max-heap keyed on squared distance (no square roots): past
// size k the farthest falls out; drained back-to-front the result is sorted.
func kClosest(_ points: [[Int]], _ k: Int) -> [[Int]] {
var heap: [(dist: Int, point: [Int])] = [] // max-heap on squared distance
func push(_ item: (dist: Int, point: [Int])) {
heap.append(item)
var child = heap.count - 1
while child > 0 {
let parent = (child - 1) / 2
if heap[parent].dist >= heap[child].dist { break }
heap.swapAt(parent, child)
child = parent
}
}
func pop() -> (dist: Int, point: [Int]) {
let top = heap[0]
heap[0] = heap[heap.count - 1]
heap.removeLast()
var parent = 0
while true {
var largest = parent
let left = 2 * parent + 1
let right = 2 * parent + 2
if left < heap.count && heap[left].dist > heap[largest].dist { largest = left }
if right < heap.count && heap[right].dist > heap[largest].dist { largest = right }
if largest == parent { break }
heap.swapAt(parent, largest)
parent = largest
}
return top
}
for point in points {
push((point[0] * point[0] + point[1] * point[1], point))
if heap.count > k { _ = pop() } // farthest falls out
}
var closest = [[Int]](repeating: [], count: heap.count)
for i in stride(from: closest.count - 1, through: 0, by: -1) {
closest[i] = pop().point
}
return closest
}
4. Kth Largest Element In An Array
Medium · LC 215
Given an unsorted integer array and k, return the kth largest element without fully sorting. Quickselect partitions around a pivot and recurses only into the side containing index n minus k, giving average O(n) time. The pitfall is pivot choice: a fixed pivot degrades to quadratic on adversarial input, so randomize it, or fall back to a size-k min-heap for guaranteed O(n log k).
def find_kth_largest(nums: list[int], k: int) -> int:
"""LC 215. Kth Largest Element in an Array.
Quickselect: partition around a pivot and recurse only into the
side containing index n - k of the sorted order. Each round keeps
an expected constant fraction of the range, so the total work is
the geometric series n + n/2 + n/4 + ... = O(n) on average; the
random pivot is what defeats the sorted-input adversary that pins
a fixed pivot at O(n^2). O(1) extra space, in place.
"""
def partition(lo: int, hi: int) -> int:
pivot_index = random.randint(lo, hi)
nums[pivot_index], nums[hi] = nums[hi], nums[pivot_index]
pivot = nums[hi]
boundary = lo # everything left of boundary is < pivot
for i in range(lo, hi):
if nums[i] < pivot:
nums[i], nums[boundary] = nums[boundary], nums[i]
boundary += 1
nums[boundary], nums[hi] = nums[hi], nums[boundary]
return boundary
target = len(nums) - k # kth largest sits at this ascending index
lo, hi = 0, len(nums) - 1
while True:
settled = partition(lo, hi)
if settled == target:
return nums[settled]
if settled < target:
lo = settled + 1
else:
hi = settled - 1
// LC 215. Quickselect: partition around a pivot and recurse only into the
// side containing index n-k of the ascending order, average O(n). The pivot
// is randomized because a fixed choice degrades to O(n^2) on adversarial
// (e.g. sorted) input.
int findKthLargest(vector<int> nums, int k) {
static mt19937 rng(random_device{}());
int targetIndex = static_cast<int>(nums.size()) - k; // position in ascending order
int lo = 0, hi = static_cast<int>(nums.size()) - 1;
while (true) {
int pivotIndex = lo + static_cast<int>(rng() % (hi - lo + 1));
swap(nums[pivotIndex], nums[hi]);
int pivot = nums[hi];
int store = lo; // Lomuto partition: everything < pivot lands left of store
for (int i = lo; i < hi; ++i)
if (nums[i] < pivot) swap(nums[i], nums[store++]);
swap(nums[store], nums[hi]);
if (store == targetIndex) return nums[store];
if (store < targetIndex) lo = store + 1;
else hi = store - 1;
}
}
/// LC 215. Quickselect for the ascending index n - k: partition around a
/// deterministic median-of-three pivot (Lomuto, pivot parked at hi) and
/// recurse only into the side containing the target, average O(n). The
/// median-of-three guards against already-sorted input degrading the pivot.
pub fn find_kth_largest(nums: Vec<i32>, k: i32) -> i32 {
let mut nums = nums;
let target = nums.len() - k as usize;
let (mut lo, mut hi) = (0usize, nums.len() - 1);
loop {
if lo == hi {
return nums[lo];
}
// Median-of-three of lo, mid, hi, then park the pivot at hi for Lomuto.
let mid = lo + (hi - lo) / 2;
if nums[mid] < nums[lo] {
nums.swap(mid, lo);
}
if nums[hi] < nums[lo] {
nums.swap(hi, lo);
}
if nums[hi] < nums[mid] {
nums.swap(hi, mid);
}
nums.swap(mid, hi);
let pivot = nums[hi];
let mut store = lo;
for i in lo..hi {
if nums[i] < pivot {
nums.swap(i, store);
store += 1;
}
}
nums.swap(store, hi); // pivot lands at its final sorted position
if store == target {
return nums[store];
} else if store < target {
lo = store + 1;
} else {
hi = store - 1;
}
}
}
/** LC 215. Quickselect toward index n - k; a random pivot defuses the adversarial quadratic case. */
export function findKthLargest(nums: number[], k: number): number {
const target = nums.length - k; // where the kth largest sits in sorted order
let lo = 0;
let hi = nums.length - 1;
for (;;) {
const pivotIndex = lo + Math.floor(Math.random() * (hi - lo + 1));
const pivot = nums[pivotIndex];
[nums[pivotIndex], nums[hi]] = [nums[hi], nums[pivotIndex]]; // park the pivot at hi
let store = lo; // everything left of store is < pivot
for (let i = lo; i < hi; i++) {
if (nums[i] < pivot) {
[nums[i], nums[store]] = [nums[store], nums[i]];
store++;
}
}
[nums[store], nums[hi]] = [nums[hi], nums[store]]; // the pivot lands in its final sorted slot
if (store === target) return nums[store];
if (store < target) lo = store + 1; // recurse only into the side holding the target
else hi = store - 1;
}
}
// LC 215. Quickselect with a random pivot: Lomuto-partition, then recurse
// into only the side holding ascending index n-k, average O(n).
func findKthLargest(nums []int, k int) int {
nums = append([]int(nil), nums...)
target := len(nums) - k // position in ascending order
lo, hi := 0, len(nums)-1
for {
pivotIndex := lo + rand.Intn(hi-lo+1)
nums[pivotIndex], nums[hi] = nums[hi], nums[pivotIndex]
pivot := nums[hi]
store := lo // everything < pivot lands left of store
for i := lo; i < hi; i++ {
if nums[i] < pivot {
nums[i], nums[store] = nums[store], nums[i]
store++
}
}
nums[store], nums[hi] = nums[hi], nums[store]
if store == target {
return nums[store]
}
if store < target {
lo = store + 1
} else {
hi = store - 1
}
}
}
// LC 215. Quickselect: Lomuto partition around a RANDOM pivot, recurse only
// into the side holding index n-k of the ascending order, average O(n).
func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
var nums = nums
let targetIndex = nums.count - k // position in ascending order
var lo = 0
var hi = nums.count - 1
while true {
let pivotIndex = Int.random(in: lo...hi)
nums.swapAt(pivotIndex, hi)
let pivot = nums[hi]
var store = lo // everything < pivot lands left of store
for i in lo..<hi where nums[i] < pivot {
nums.swapAt(i, store)
store += 1
}
nums.swapAt(store, hi)
if store == targetIndex { return nums[store] }
if store < targetIndex { lo = store + 1 } else { hi = store - 1 }
}
}
5. Task Scheduler
Medium · LC 621
Given task labels and a cooldown n that must separate identical tasks, return the minimum number of CPU intervals, idle slots included, needed to finish them all. Count frequencies, find the maximum frequency f and the number of tasks tied at f, then compute (f-1)*(n+1) plus the tie count. Floor the answer at the total task count, because with enough distinct tasks every idle slot fills and the formula undercounts.
def least_interval(tasks: list[str], n: int) -> int:
"""LC 621. Task Scheduler.
Count frequencies and let f be the maximum. The hottest task forces
f - 1 frames of width n + 1 (the task plus its cooldown), and every
task tied at f adds one final slot after the last frame; hence
(f - 1) * (n + 1) + ties. Floor at len(tasks): with enough distinct
tasks every idle slot fills and the formula undercounts. O(n) time,
O(1) space (at most 26 labels).
"""
counts = Counter(tasks)
max_freq = max(counts.values())
ties = sum(1 for count in counts.values() if count == max_freq)
return max(len(tasks), (max_freq - 1) * (n + 1) + ties)
// LC 621. Frame formula: the max-frequency task forces (f-1) frames of width
// n+1, plus one final slot per task tied at frequency f. With enough distinct
// tasks every idle slot fills and the formula undercounts, so floor the
// answer at the total task count.
int leastInterval(vector<char> tasks, int n) {
int counts[26] = {};
for (char task : tasks) ++counts[task - 'A'];
int maxFreq = 0, tiedAtMax = 0;
for (int count : counts) {
if (count > maxFreq) {
maxFreq = count;
tiedAtMax = 1;
} else if (count == maxFreq && count > 0) {
++tiedAtMax;
}
}
int framed = (maxFreq - 1) * (n + 1) + tiedAtMax;
return max(static_cast<int>(tasks.size()), framed);
}
/// LC 621. Frame formula -- no heap needed. The max-frequency task f forms
/// f - 1 frames of width n + 1, and every task tied at f appends one slot
/// to the last frame: (f - 1) * (n + 1) + ties. With enough distinct tasks
/// all idle slots fill and the formula undercounts, so floor at tasks.len().
pub fn least_interval(tasks: Vec<char>, n: i32) -> i32 {
let total = tasks.len() as i32;
let mut counts = [0i32; 26];
for task in tasks {
counts[(task as u8 - b'A') as usize] += 1;
}
let max_freq = *counts.iter().max().unwrap();
let ties = counts.iter().filter(|&&c| c == max_freq).count() as i32;
((max_freq - 1) * (n + 1) + ties).max(total)
}
/** LC 621. Frame formula: (maxCount - 1) frames of width n + 1, plus the letters tied at maxCount. */
export function leastInterval(tasks: string[], n: number): number {
const counts = new Array<number>(26).fill(0);
for (const task of tasks) counts[task.charCodeAt(0) - 65]++;
const maxCount = Math.max(...counts);
const maxTies = counts.filter((count) => count === maxCount).length;
// with enough distinct tasks every idle slot fills, so the answer never drops below tasks.length
return Math.max(tasks.length, (maxCount - 1) * (n + 1) + maxTies);
}
// LC 621. Frame formula: (maxFreq-1)*(n+1) plus one slot per task tied at
// maxFreq, floored at the task count once every idle slot fills.
func leastInterval(tasks []byte, n int) int {
counts := [26]int{}
for _, task := range tasks {
counts[task-'A']++
}
maxFreq, tiedAtMax := 0, 0
for _, count := range counts {
if count > maxFreq {
maxFreq, tiedAtMax = count, 1
} else if count == maxFreq && count > 0 {
tiedAtMax++
}
}
framed := (maxFreq-1)*(n+1) + tiedAtMax
if len(tasks) > framed {
return len(tasks)
}
return framed
}
// LC 621. Frame formula: (maxFreq - 1) frames of width n+1 plus one slot per
// task tied at the max, floored at the total task count.
func leastInterval(_ tasks: [Character], _ n: Int) -> Int {
var counts = [Int](repeating: 0, count: 26)
for task in tasks { counts[Int(task.asciiValue!) - 65] += 1 } // 65 == "A"
var maxFreq = 0
var tiedAtMax = 0
for count in counts {
if count > maxFreq {
maxFreq = count
tiedAtMax = 1
} else if count == maxFreq && count > 0 {
tiedAtMax += 1
}
}
let framed = (maxFreq - 1) * (n + 1) + tiedAtMax
return max(tasks.count, framed)
}
6. Design Twitter
Medium · LC 355
Design a class supporting postTweet, follow, unfollow, and getNewsFeed, where the feed returns the 10 most recent tweets from the user and everyone they follow. Store per-user tweet lists stamped with a global timestamp, and on getNewsFeed merge the relevant lists with a max-heap, popping up to ten times. Seed the heap with each list's newest tweet and after each pop push that author's next older one, the standard k-way merge.
class Twitter:
"""LC 355. Design Twitter.
Per-user tweet lists stamped with a global timestamp, plus follow
sets. get_news_feed is a k-way merge: seed a max-heap with each
relevant timeline's newest tweet, and after every pop push that
same author's next older tweet, stopping after ten pops. Posting
and (un)following are O(1); a feed costs O(f log f) for f followees
since at most f + 10 heap operations happen.
"""
def __init__(self) -> None:
self._clock = 0
self._timelines: dict[int, list[tuple[int, int]]] = defaultdict(list)
self._following: dict[int, set[int]] = defaultdict(set)
def post_tweet(self, user_id: int, tweet_id: int) -> None:
self._timelines[user_id].append((self._clock, tweet_id))
self._clock += 1
def get_news_feed(self, user_id: int) -> list[int]:
sources = self._following[user_id] | {user_id}
merge_heap: list[tuple[int, int, int, int]] = []
for author in sources:
timeline = self._timelines[author]
if timeline:
newest = len(timeline) - 1
stamp, tweet_id = timeline[newest]
merge_heap.append((-stamp, tweet_id, author, newest))
heapq.heapify(merge_heap)
feed: list[int] = []
while merge_heap and len(feed) < 10:
_, tweet_id, author, index = heapq.heappop(merge_heap)
feed.append(tweet_id)
if index > 0: # replace the popped tweet with the author's next older one
stamp, older_id = self._timelines[author][index - 1]
heapq.heappush(merge_heap, (-stamp, older_id, author, index - 1))
return feed
def follow(self, follower_id: int, followee_id: int) -> None:
if follower_id != followee_id: # self is merged into every feed anyway
self._following[follower_id].add(followee_id)
def unfollow(self, follower_id: int, followee_id: int) -> None:
self._following[follower_id].discard(followee_id)
// LC 355. Per-user tweet vectors stamped with a global timestamp; getNewsFeed
// is a k-way merge: seed a max-heap with each relevant list's newest tweet,
// and after each of at most 10 pops push that author's next older one.
class Twitter {
long long clock = 0;
unordered_map<int, vector<pair<long long, int>>> tweetsOf; // userId -> (timestamp, tweetId)
unordered_map<int, unordered_set<int>> followeesOf;
public:
void postTweet(int userId, int tweetId) { tweetsOf[userId].push_back({clock++, tweetId}); }
vector<int> getNewsFeed(int userId) {
priority_queue<tuple<long long, int, int, int>> newestFirst; // (timestamp, tweetId, authorId, index)
auto seed = [&](int author) {
auto it = tweetsOf.find(author);
if (it == tweetsOf.end() || it->second.empty()) return;
int last = static_cast<int>(it->second.size()) - 1;
newestFirst.push({it->second[last].first, it->second[last].second, author, last});
};
seed(userId);
for (int followee : followeesOf[userId])
if (followee != userId) seed(followee); // don't seed self twice
vector<int> feed;
while (!newestFirst.empty() && feed.size() < 10) {
auto [timestamp, tweetId, author, index] = newestFirst.top();
newestFirst.pop();
feed.push_back(tweetId);
if (index > 0) { // push this author's next older tweet
const pair<long long, int>& older = tweetsOf[author][index - 1];
newestFirst.push({older.first, older.second, author, index - 1});
}
}
return feed;
}
void follow(int followerId, int followeeId) { followeesOf[followerId].insert(followeeId); }
void unfollow(int followerId, int followeeId) { followeesOf[followerId].erase(followeeId); }
};
/// LC 355. Per-user tweet lists stamped with a global i64 clock plus a
/// follow-set map. get_news_feed is a k-way merge: seed a max-heap with
/// each relevant author's newest tweet (time, id, author, index), and after
/// every pop push that author's next older tweet, stopping at 10 tweets.
pub struct Twitter {
clock: i64,
tweets: HashMap<i32, Vec<(i64, i32)>>,
follows: HashMap<i32, HashSet<i32>>,
}
impl Twitter {
pub fn new() -> Self {
Twitter { clock: 0, tweets: HashMap::new(), follows: HashMap::new() }
}
pub fn post_tweet(&mut self, user_id: i32, tweet_id: i32) {
self.clock += 1;
self.tweets.entry(user_id).or_default().push((self.clock, tweet_id));
}
pub fn get_news_feed(&self, user_id: i32) -> Vec<i32> {
let mut authors = self.follows.get(&user_id).cloned().unwrap_or_default();
authors.insert(user_id); // a user always sees their own tweets
let mut newest_first: BinaryHeap<(i64, i32, i32, usize)> = BinaryHeap::new();
for &author in &authors {
if let Some(list) = self.tweets.get(&author) {
let idx = list.len() - 1;
let (time, tweet_id) = list[idx];
newest_first.push((time, tweet_id, author, idx));
}
}
let mut feed = Vec::with_capacity(10);
while feed.len() < 10 {
match newest_first.pop() {
None => break,
Some((_, tweet_id, author, idx)) => {
feed.push(tweet_id);
if idx > 0 {
// Replace the popped tweet with the same author's next older one.
let (time, id) = self.tweets[&author][idx - 1];
newest_first.push((time, id, author, idx - 1));
}
}
}
}
feed
}
pub fn follow(&mut self, follower_id: i32, followee_id: i32) {
self.follows.entry(follower_id).or_default().insert(followee_id);
}
pub fn unfollow(&mut self, follower_id: i32, followee_id: i32) {
if let Some(followees) = self.follows.get_mut(&follower_id) {
followees.remove(&followee_id);
}
}
}
/** LC 355. Per-user tweet lists with global timestamps; the feed is a 10-pop k-way merge via max-heap. */
export class Twitter {
private clock = 0; // global timestamp shared by every tweet
private tweetsOf = new Map<number, [number, number][]>(); // userId -> [time, tweetId], oldest first
private followsOf = new Map<number, Set<number>>();
postTweet(userId: number, tweetId: number): void {
let tweets = this.tweetsOf.get(userId);
if (tweets === undefined) {
tweets = [];
this.tweetsOf.set(userId, tweets);
}
tweets.push([this.clock++, tweetId]);
}
getNewsFeed(userId: number): number[] {
// entries: [time, tweetId, author's tweet list, position in that list]; max-heap on time
type Entry = [number, number, [number, number][], number];
const heap: Entry[] = [];
const push = (entry: Entry): void => {
heap.push(entry);
let child = heap.length - 1;
while (child > 0) {
const parent = (child - 1) >> 1;
if (heap[parent][0] >= heap[child][0]) break;
[heap[parent], heap[child]] = [heap[child], heap[parent]];
child = parent;
}
};
const pop = (): Entry => {
const top = heap[0];
const last = heap.pop()!;
if (heap.length > 0) {
heap[0] = last;
let parent = 0;
for (;;) {
let newest = parent;
const left = 2 * parent + 1;
const right = 2 * parent + 2;
if (left < heap.length && heap[left][0] > heap[newest][0]) newest = left;
if (right < heap.length && heap[right][0] > heap[newest][0]) newest = right;
if (newest === parent) break;
[heap[parent], heap[newest]] = [heap[newest], heap[parent]];
parent = newest;
}
}
return top;
};
const authors = new Set(this.followsOf.get(userId) ?? []);
authors.add(userId); // a user always sees their own tweets
for (const author of authors) {
const tweets = this.tweetsOf.get(author);
if (tweets !== undefined && tweets.length > 0) {
const newest = tweets.length - 1;
push([tweets[newest][0], tweets[newest][1], tweets, newest]); // seed each list's newest tweet
}
}
const feed: number[] = [];
while (heap.length > 0 && feed.length < 10) {
const [, tweetId, tweets, position] = pop();
feed.push(tweetId);
// the popped author's next older tweet refills the heap, the standard k-way merge step
if (position > 0) push([tweets[position - 1][0], tweets[position - 1][1], tweets, position - 1]);
}
return feed;
}
follow(followerId: number, followeeId: number): void {
let follows = this.followsOf.get(followerId);
if (follows === undefined) {
follows = new Set();
this.followsOf.set(followerId, follows);
}
follows.add(followeeId);
}
unfollow(followerId: number, followeeId: number): void {
this.followsOf.get(followerId)?.delete(followeeId);
}
}
// LC 355. Per-user timelines stamped by a global clock; getNewsFeed is a
// k-way merge seeding a max-heap with each relevant timeline's newest tweet.
type Twitter struct {
clock int
tweetsOf map[int][][2]int // userId -> (timestamp, tweetId)
followees map[int]map[int]bool
}
func newTwitter() *Twitter {
return &Twitter{tweetsOf: map[int][][2]int{}, followees: map[int]map[int]bool{}}
}
func (tw *Twitter) postTweet(userID, tweetID int) {
tw.tweetsOf[userID] = append(tw.tweetsOf[userID], [2]int{tw.clock, tweetID})
tw.clock++
}
func (tw *Twitter) getNewsFeed(userID int) []int {
heap := [][4]int{} // (timestamp, tweetId, authorId, index), newest on top
push := func(e [4]int) {
heap = append(heap, e)
for i := len(heap) - 1; i > 0; {
parent := (i - 1) / 2
if heap[parent][0] >= heap[i][0] {
break
}
heap[i], heap[parent] = heap[parent], heap[i]
i = parent
}
}
pop := func() [4]int {
top := heap[0]
last := len(heap) - 1
heap[0] = heap[last]
heap = heap[:last]
for i := 0; ; {
next := i
if l := 2*i + 1; l < len(heap) && heap[l][0] > heap[next][0] {
next = l
}
if r := 2*i + 2; r < len(heap) && heap[r][0] > heap[next][0] {
next = r
}
if next == i {
break
}
heap[i], heap[next] = heap[next], heap[i]
i = next
}
return top
}
seed := func(author int) {
timeline := tw.tweetsOf[author]
if len(timeline) == 0 {
return
}
last := len(timeline) - 1
push([4]int{timeline[last][0], timeline[last][1], author, last})
}
seed(userID)
for followee := range tw.followees[userID] {
if followee != userID { // don't seed self twice
seed(followee)
}
}
feed := []int{}
for len(heap) > 0 && len(feed) < 10 {
top := pop()
feed = append(feed, top[1])
if top[3] > 0 { // push this author's next older tweet
older := tw.tweetsOf[top[2]][top[3]-1]
push([4]int{older[0], older[1], top[2], top[3] - 1})
}
}
return feed
}
func (tw *Twitter) follow(followerID, followeeID int) {
if tw.followees[followerID] == nil {
tw.followees[followerID] = map[int]bool{}
}
tw.followees[followerID][followeeID] = true
}
func (tw *Twitter) unfollow(followerID, followeeID int) {
delete(tw.followees[followerID], followeeID)
}
// LC 355. Per-user timelines stamped with a global clock; getNewsFeed is a
// k-way merge: seed a max-heap with each relevant timeline's newest tweet and
// push that author's next older one after each of at most 10 pops.
class Twitter {
private var clock = 0
private var tweetsOf: [Int: [(stamp: Int, id: Int)]] = [:]
private var followeesOf: [Int: Set<Int>] = [:]
func postTweet(_ userId: Int, _ tweetId: Int) {
tweetsOf[userId, default: []].append((clock, tweetId))
clock += 1
}
func getNewsFeed(_ userId: Int) -> [Int] {
var heap: [(Int, Int, Int, Int)] = [] // max-heap of (stamp, tweetId, author, index)
func push(_ item: (Int, Int, Int, Int)) {
heap.append(item)
var child = heap.count - 1
while child > 0 {
let parent = (child - 1) / 2
if heap[parent].0 >= heap[child].0 { break }
heap.swapAt(parent, child)
child = parent
}
}
func pop() -> (Int, Int, Int, Int) {
let top = heap[0]
heap[0] = heap[heap.count - 1]
heap.removeLast()
var parent = 0
while true {
var largest = parent
let left = 2 * parent + 1
let right = 2 * parent + 2
if left < heap.count && heap[left].0 > heap[largest].0 { largest = left }
if right < heap.count && heap[right].0 > heap[largest].0 { largest = right }
if largest == parent { break }
heap.swapAt(parent, largest)
parent = largest
}
return top
}
func seed(_ author: Int) {
guard let timeline = tweetsOf[author], !timeline.isEmpty else { return }
let last = timeline.count - 1
push((timeline[last].stamp, timeline[last].id, author, last))
}
seed(userId)
for followee in followeesOf[userId] ?? [] where followee != userId {
seed(followee) // don't seed self twice
}
var feed: [Int] = []
while !heap.isEmpty && feed.count < 10 {
let (_, tweetId, author, index) = pop()
feed.append(tweetId)
if index > 0 { // push this author's next older tweet
let older = tweetsOf[author]![index - 1]
push((older.stamp, older.id, author, index - 1))
}
}
return feed
}
func follow(_ followerId: Int, _ followeeId: Int) {
followeesOf[followerId, default: []].insert(followeeId)
}
func unfollow(_ followerId: Int, _ followeeId: Int) {
followeesOf[followerId]?.remove(followeeId)
}
}
7. Single Threaded CPU
Medium · LC 1834
Given tasks with enqueue times and processing durations, return the order a single-threaded CPU executes them when it always runs the shortest available task, ties broken by lower index. Sort by enqueue time, sweep a clock forward, push all arrived tasks into a min-heap keyed by duration then index, and pop the next task to run. When the heap is empty, jump the clock straight to the next arrival, and keep original indices when sorting.
def get_order(tasks: list[list[int]]) -> list[int]:
"""LC 1834. Single-Threaded CPU.
Sort tasks by arrival (keeping original indices), then sweep a
clock forward: admit every task that has arrived into a min-heap
keyed (duration, index) and run the heap root to completion. When
the heap is empty the CPU is idle, so jump the clock straight to
the next arrival instead of ticking. O(n log n) time, O(n) space.
"""
arrivals = sorted(
(enqueue, duration, i) for i, (enqueue, duration) in enumerate(tasks)
)
available: list[tuple[int, int]] = [] # (duration, original index)
order: list[int] = []
clock = 0
admitted = 0
while len(order) < len(tasks):
while admitted < len(arrivals) and arrivals[admitted][0] <= clock:
_, duration, i = arrivals[admitted]
heapq.heappush(available, (duration, i))
admitted += 1
if not available:
clock = arrivals[admitted][0] # idle jump: nothing runnable until then
continue
duration, i = heapq.heappop(available)
order.append(i)
clock += duration
return order
// LC 1834. Sort indices by enqueue time, sweep a long long clock forward,
// pushing every arrived task into a min-heap keyed by (duration, index) and
// popping the next to run. An empty heap jumps the clock straight to the
// next arrival.
vector<int> getOrder(vector<vector<int>> tasks) {
int n = static_cast<int>(tasks.size());
vector<int> byArrival(n);
iota(byArrival.begin(), byArrival.end(), 0);
sort(byArrival.begin(), byArrival.end(), [&](int a, int b) {
return tasks[a][0] != tasks[b][0] ? tasks[a][0] < tasks[b][0] : a < b;
});
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> ready; // (duration, index)
vector<int> order;
long long clock = 0; // sums of durations can exceed int range
int next = 0;
while (static_cast<int>(order.size()) < n) {
if (ready.empty() && clock < tasks[byArrival[next]][0])
clock = tasks[byArrival[next]][0]; // idle CPU jumps to the next arrival
while (next < n && tasks[byArrival[next]][0] <= clock) {
ready.push({tasks[byArrival[next]][1], byArrival[next]});
++next;
}
auto [duration, index] = ready.top();
ready.pop();
clock += duration;
order.push_back(index);
}
return order;
}
/// LC 1834. Sort tasks by arrival (keeping original indices), sweep an i64
/// clock, and push every arrived task into a Reverse min-heap keyed by
/// (duration, index) -- exactly the CPU's tie-break. When the heap is empty
/// the CPU idles, so jump the clock straight to the next arrival.
pub fn get_order(tasks: Vec<Vec<i32>>) -> Vec<i32> {
let mut by_arrival: Vec<(i64, i64, usize)> = tasks
.iter()
.enumerate()
.map(|(i, t)| (t[0] as i64, t[1] as i64, i))
.collect();
by_arrival.sort_unstable();
let mut available: BinaryHeap<Reverse<(i64, usize)>> = BinaryHeap::new();
let mut order = Vec::with_capacity(by_arrival.len());
let mut clock: i64 = 0;
let mut next = 0;
while order.len() < by_arrival.len() {
if available.is_empty() && clock < by_arrival[next].0 {
clock = by_arrival[next].0; // idle: jump to the next arrival
}
while next < by_arrival.len() && by_arrival[next].0 <= clock {
let (_, duration, index) = by_arrival[next];
available.push(Reverse((duration, index)));
next += 1;
}
let Reverse((duration, index)) = available.pop().unwrap();
clock += duration;
order.push(index as i32);
}
order
}
/** LC 1834. Sort by arrival, sweep a clock; a min-heap on (duration, index) picks each next task. */
export function getOrder(tasks: number[][]): number[] {
const byArrival = tasks.map((_, index) => index).sort((a, b) => tasks[a][0] - tasks[b][0]);
const heap: number[] = []; // task indices; min-heap keyed by (duration, then original index)
const before = (a: number, b: number): boolean =>
tasks[a][1] !== tasks[b][1] ? tasks[a][1] < tasks[b][1] : a < b;
const push = (task: number): void => {
heap.push(task);
let child = heap.length - 1;
while (child > 0) {
const parent = (child - 1) >> 1;
if (!before(heap[child], heap[parent])) break;
[heap[parent], heap[child]] = [heap[child], heap[parent]];
child = parent;
}
};
const pop = (): number => {
const top = heap[0];
const last = heap.pop()!;
if (heap.length > 0) {
heap[0] = last;
let parent = 0;
for (;;) {
let least = parent;
const left = 2 * parent + 1;
const right = 2 * parent + 2;
if (left < heap.length && before(heap[left], heap[least])) least = left;
if (right < heap.length && before(heap[right], heap[least])) least = right;
if (least === parent) break;
[heap[parent], heap[least]] = [heap[least], heap[parent]];
parent = least;
}
}
return top;
};
const order: number[] = [];
let clock = 0;
let next = 0; // next unprocessed position in byArrival
while (order.length < tasks.length) {
if (heap.length === 0 && clock < tasks[byArrival[next]][0]) {
clock = tasks[byArrival[next]][0]; // an idle CPU jumps straight to the next arrival
}
while (next < byArrival.length && tasks[byArrival[next]][0] <= clock) push(byArrival[next++]);
const task = pop();
order.push(task);
clock += tasks[task][1];
}
return order;
}
// LC 1834. Sort indices by arrival and sweep a clock: admit arrived tasks
// into a (duration, index) min-heap, run the root, idle-jump when empty.
func getOrder(tasks [][]int) []int {
n := len(tasks)
byArrival := make([]int, n)
for i := range byArrival {
byArrival[i] = i
}
sort.Slice(byArrival, func(a, b int) bool {
if tasks[byArrival[a]][0] != tasks[byArrival[b]][0] {
return tasks[byArrival[a]][0] < tasks[byArrival[b]][0]
}
return byArrival[a] < byArrival[b]
})
heap := [][2]int{} // (duration, original index)
less := func(a, b [2]int) bool {
if a[0] != b[0] {
return a[0] < b[0]
}
return a[1] < b[1]
}
push := func(e [2]int) {
heap = append(heap, e)
for i := len(heap) - 1; i > 0; {
parent := (i - 1) / 2
if !less(heap[i], heap[parent]) {
break
}
heap[i], heap[parent] = heap[parent], heap[i]
i = parent
}
}
pop := func() [2]int {
top := heap[0]
last := len(heap) - 1
heap[0] = heap[last]
heap = heap[:last]
for i := 0; ; {
next := i
if l := 2*i + 1; l < len(heap) && less(heap[l], heap[next]) {
next = l
}
if r := 2*i + 2; r < len(heap) && less(heap[r], heap[next]) {
next = r
}
if next == i {
break
}
heap[i], heap[next] = heap[next], heap[i]
i = next
}
return top
}
order := make([]int, 0, n)
clock, next := 0, 0
for len(order) < n {
if len(heap) == 0 && clock < tasks[byArrival[next]][0] {
clock = tasks[byArrival[next]][0] // idle CPU jumps to the next arrival
}
for next < n && tasks[byArrival[next]][0] <= clock {
push([2]int{tasks[byArrival[next]][1], byArrival[next]})
next++
}
top := pop()
clock += top[0]
order = append(order, top[1])
}
return order
}
// LC 1834. Sort indices by arrival and sweep a clock: admit every arrived
// task into a min-heap on (duration, index); an idle CPU jumps the clock
// straight to the next arrival.
func getOrder(_ tasks: [[Int]]) -> [Int] {
let n = tasks.count
let byArrival = (0..<n).sorted {
tasks[$0][0] != tasks[$1][0] ? tasks[$0][0] < tasks[$1][0] : $0 < $1
}
var heap: [(Int, Int)] = [] // min-heap of (duration, original index)
func push(_ item: (Int, Int)) {
heap.append(item)
var child = heap.count - 1
while child > 0 {
let parent = (child - 1) / 2
if heap[parent] <= heap[child] { break }
heap.swapAt(parent, child)
child = parent
}
}
func pop() -> (Int, Int) {
let top = heap[0]
heap[0] = heap[heap.count - 1]
heap.removeLast()
var parent = 0
while true {
var smallest = parent
let left = 2 * parent + 1
let right = 2 * parent + 2
if left < heap.count && heap[left] < heap[smallest] { smallest = left }
if right < heap.count && heap[right] < heap[smallest] { smallest = right }
if smallest == parent { break }
heap.swapAt(parent, smallest)
parent = smallest
}
return top
}
var order: [Int] = []
var clock = 0
var next = 0
while order.count < n {
if heap.isEmpty && clock < tasks[byArrival[next]][0] {
clock = tasks[byArrival[next]][0] // idle CPU jumps to the next arrival
}
while next < n && tasks[byArrival[next]][0] <= clock {
push((tasks[byArrival[next]][1], byArrival[next]))
next += 1
}
let (duration, index) = pop()
clock += duration
order.append(index)
}
return order
}
8. Reorganize String
Medium · LC 767
Given a string, rearrange its characters so no two adjacent characters are equal, returning any valid arrangement or the empty string if impossible. Greedily build the answer with a max-heap of letter counts: pop the most frequent letter, append it, and only push it back after the next pop. Holding back the just-used letter enforces the spacing; impossibility happens exactly when one letter's count exceeds (n+1)/2.
def reorganize_string(s: str) -> str:
"""LC 767. Reorganize String.
Greedy with a max-heap of letter counts: always append the most
frequent letter still allowed, holding the just-used letter out of
the heap for one round so it can never repeat. If the heap runs dry
while a held letter still has copies, one count exceeded
(n + 1) // 2 and no arrangement exists. O(n log 26) time, O(1)
heap space.
"""
counts = Counter(s)
by_count: list[tuple[int, str]] = [(-count, ch) for ch, count in counts.items()]
heapq.heapify(by_count)
built: list[str] = []
held: tuple[int, str] | None = None # the letter just used, banned this round
while by_count:
neg_count, ch = heapq.heappop(by_count)
built.append(ch)
if held:
heapq.heappush(by_count, held) # one round has passed; it is legal again
held = (neg_count + 1, ch) if neg_count + 1 < 0 else None
return "" if held else "".join(built) # stranded copies mean impossible
// LC 767. Greedy with a max-heap of letter counts and a hold-back: append the
// most frequent letter, but only push it back after the next pop, which
// forces a gap of one between repeats. If letters run out while the held
// letter still has copies, one count exceeded (n+1)/2 and it's impossible.
string reorganizeString(string s) {
int counts[26] = {};
for (char ch : s) ++counts[ch - 'a'];
priority_queue<pair<int, char>> heap; // (remaining count, letter)
for (int i = 0; i < 26; ++i)
if (counts[i] > 0) heap.push({counts[i], static_cast<char>('a' + i)});
string result;
pair<int, char> held = {0, 0}; // just-used letter, banned for one round
while (!heap.empty()) {
auto [count, letter] = heap.top();
heap.pop();
result += letter;
if (held.first > 0) heap.push(held); // previous letter becomes legal again
held = {count - 1, letter};
}
return result.size() == s.size() ? result : "";
}
/// LC 767. Greedy with a max-heap of (count, letter): pop the most
/// frequent letter, append it, and HOLD IT BACK -- it only re-enters the
/// heap after the next different letter is placed, which enforces the
/// spacing. A letter still held when the heap empties means its count
/// exceeded (n + 1) / 2 and no arrangement exists.
pub fn reorganize_string(s: String) -> String {
let mut counts = [0i32; 26];
for b in s.bytes() {
counts[(b - b'a') as usize] += 1;
}
let mut heap: BinaryHeap<(i32, u8)> = counts
.iter()
.enumerate()
.filter(|&(_, &count)| count > 0)
.map(|(i, &count)| (count, b'a' + i as u8))
.collect();
let mut result = Vec::with_capacity(s.len());
let mut held: Option<(i32, u8)> = None;
while let Some((count, letter)) = heap.pop() {
result.push(letter);
if let Some(previous) = held.take() {
heap.push(previous); // the prior letter is now safe to reuse
}
if count > 1 {
held = Some((count - 1, letter));
}
}
if held.is_some() {
return String::new(); // copies remain but every placement would touch itself
}
String::from_utf8(result).unwrap()
}
/** LC 767. Max-heap of letter counts; hold the just-used letter out for one pop to force spacing. */
export function reorganizeString(s: string): string {
const countOf = new Map<string, number>();
for (const ch of s) countOf.set(ch, (countOf.get(ch) ?? 0) + 1);
const heap: [number, string][] = []; // max-heap by remaining count
const push = (entry: [number, string]): void => {
heap.push(entry);
let child = heap.length - 1;
while (child > 0) {
const parent = (child - 1) >> 1;
if (heap[parent][0] >= heap[child][0]) break;
[heap[parent], heap[child]] = [heap[child], heap[parent]];
child = parent;
}
};
const pop = (): [number, string] => {
const top = heap[0];
const last = heap.pop()!;
if (heap.length > 0) {
heap[0] = last;
let parent = 0;
for (;;) {
let most = parent;
const left = 2 * parent + 1;
const right = 2 * parent + 2;
if (left < heap.length && heap[left][0] > heap[most][0]) most = left;
if (right < heap.length && heap[right][0] > heap[most][0]) most = right;
if (most === parent) break;
[heap[parent], heap[most]] = [heap[most], heap[parent]];
parent = most;
}
}
return top;
};
for (const [ch, count] of countOf) push([count, ch]);
const pieces: string[] = [];
let held: [number, string] | null = null; // the just-used letter, banned for exactly one pop
while (heap.length > 0) {
const [count, ch] = pop();
pieces.push(ch);
if (held !== null) push(held); // a different letter went between, so it is legal again
held = count > 1 ? [count - 1, ch] : null;
}
// a leftover held letter means some count exceeded (n + 1) / 2, so no arrangement exists
return held === null ? pieces.join("") : "";
}
// LC 767. Max-heap of letter counts with a one-round hold-back on the letter
// just used; if copies are stranded when the heap drains, it's impossible.
func reorganizeString(s string) string {
counts := [26]int{}
for i := 0; i < len(s); i++ {
counts[s[i]-'a']++
}
heap := [][2]int{} // (remaining count, letter)
higher := func(a, b [2]int) bool {
if a[0] != b[0] {
return a[0] > b[0]
}
return a[1] > b[1]
}
push := func(e [2]int) {
heap = append(heap, e)
for i := len(heap) - 1; i > 0; {
parent := (i - 1) / 2
if !higher(heap[i], heap[parent]) {
break
}
heap[i], heap[parent] = heap[parent], heap[i]
i = parent
}
}
pop := func() [2]int {
top := heap[0]
last := len(heap) - 1
heap[0] = heap[last]
heap = heap[:last]
for i := 0; ; {
next := i
if l := 2*i + 1; l < len(heap) && higher(heap[l], heap[next]) {
next = l
}
if r := 2*i + 2; r < len(heap) && higher(heap[r], heap[next]) {
next = r
}
if next == i {
break
}
heap[i], heap[next] = heap[next], heap[i]
i = next
}
return top
}
for i := 0; i < 26; i++ {
if counts[i] > 0 {
push([2]int{counts[i], 'a' + i})
}
}
result := make([]byte, 0, len(s))
held := [2]int{} // just-used letter, banned for one round
for len(heap) > 0 {
top := pop()
result = append(result, byte(top[1]))
if held[0] > 0 {
push(held) // previous letter becomes legal again
}
held = [2]int{top[0] - 1, top[1]}
}
if len(result) != len(s) {
return "" // stranded copies: one count exceeded (n+1)/2
}
return string(result)
}
// LC 767. Max-heap greedy with a hold-back: append the most frequent letter,
// but only requeue it after the next pop, forcing a gap of one between
// repeats. Stranded copies at the end mean one count exceeded (n+1)/2.
func reorganizeString(_ s: String) -> String {
var counts = [Int](repeating: 0, count: 26)
for scalar in s.unicodeScalars { counts[Int(scalar.value) - 97] += 1 } // 97 == "a"
var heap: [(Int, Int)] = [] // max-heap of (remaining count, letter index)
func push(_ item: (Int, Int)) {
heap.append(item)
var child = heap.count - 1
while child > 0 {
let parent = (child - 1) / 2
if heap[parent] >= heap[child] { break }
heap.swapAt(parent, child)
child = parent
}
}
func pop() -> (Int, Int) {
let top = heap[0]
heap[0] = heap[heap.count - 1]
heap.removeLast()
var parent = 0
while true {
var largest = parent
let left = 2 * parent + 1
let right = 2 * parent + 2
if left < heap.count && heap[left] > heap[largest] { largest = left }
if right < heap.count && heap[right] > heap[largest] { largest = right }
if largest == parent { break }
heap.swapAt(parent, largest)
parent = largest
}
return top
}
for i in 0..<26 where counts[i] > 0 { push((counts[i], i)) }
var result: [Character] = []
var held = (0, 0) // just-used letter, banned for one round
while !heap.isEmpty {
let (count, letter) = pop()
result.append(Character(UnicodeScalar(UInt8(97 + letter))))
if held.0 > 0 { push(held) } // previous letter becomes legal again
held = (count - 1, letter)
}
return result.count == s.count ? String(result) : ""
}
9. Longest Happy String
Medium · LC 1405
Given counts a, b, and c, build the longest string from those three letters that never contains three identical letters in a row. Use a max-heap by remaining count: pop the most plentiful letter, but if appending it would create a triple, take the second-best letter instead. The hold-back caps every run at two, and the string ends cleanly when only a triple-forcing letter remains in the heap.
def longest_diverse_string(a: int, b: int, c: int) -> str:
"""LC 1405. Longest Happy String.
Same hold-back greedy as reorganize_string but with a run cap of 2:
pop the most plentiful letter, and if appending it would make three
in a row, take the runner-up instead and push the blocked letter
back untouched. When only the triple-forcing letter remains, the
string ends cleanly. O(a + b + c) time, O(1) space.
"""
by_count: list[tuple[int, str]] = [
(-count, ch) for count, ch in ((a, "a"), (b, "b"), (c, "c")) if count > 0
]
heapq.heapify(by_count)
built: list[str] = []
while by_count:
neg_count, ch = heapq.heappop(by_count)
if len(built) >= 2 and built[-1] == built[-2] == ch:
if not by_count: # only the run-breaking letter is left: stop here
break
neg_runner_up, runner_up = heapq.heappop(by_count)
built.append(runner_up)
if neg_runner_up + 1 < 0:
heapq.heappush(by_count, (neg_runner_up + 1, runner_up))
heapq.heappush(by_count, (neg_count, ch)) # blocked letter, count unchanged
else:
built.append(ch)
if neg_count + 1 < 0:
heapq.heappush(by_count, (neg_count + 1, ch))
return "".join(built)
// LC 1405. Max-heap by remaining count: take the most plentiful letter unless
// it would make a triple, in which case take the second-best instead and
// requeue the first. If only the triple-forcing letter remains, the string
// ends cleanly.
string longestDiverseString(int a, int b, int c) {
priority_queue<pair<int, char>> heap; // (remaining count, letter)
if (a > 0) heap.push({a, 'a'});
if (b > 0) heap.push({b, 'b'});
if (c > 0) heap.push({c, 'c'});
string result;
while (!heap.empty()) {
auto [count, letter] = heap.top();
heap.pop();
if (result.size() >= 2 && result.back() == letter && result[result.size() - 2] == letter) {
if (heap.empty()) break; // only the triple-forcing letter remains
auto [secondCount, secondLetter] = heap.top();
heap.pop();
result += secondLetter;
if (secondCount > 1) heap.push({secondCount - 1, secondLetter});
heap.push({count, letter}); // best letter waits one slot
} else {
result += letter;
if (count > 1) heap.push({count - 1, letter});
}
}
return result;
}
/// LC 1405. Max-heap by remaining count over the three letters: pop the
/// most plentiful, but when appending it would make a triple, take the
/// second-best instead and push the first back. If no second letter
/// exists, the string ends cleanly; the hold-back caps every run at two.
pub fn longest_diverse_string(a: i32, b: i32, c: i32) -> String {
let mut heap: BinaryHeap<(i32, u8)> = BinaryHeap::new();
for (count, letter) in [(a, b'a'), (b, b'b'), (c, b'c')] {
if count > 0 {
heap.push((count, letter));
}
}
let mut result: Vec<u8> = Vec::new();
while let Some((count, letter)) = heap.pop() {
let would_triple = result.len() >= 2
&& result[result.len() - 1] == letter
&& result[result.len() - 2] == letter;
if would_triple {
// Only the triple-forcing letter remains: the string is done.
let (other_count, other_letter) = match heap.pop() {
None => break,
Some(second_best) => second_best,
};
result.push(other_letter);
if other_count > 1 {
heap.push((other_count - 1, other_letter));
}
heap.push((count, letter));
} else {
result.push(letter);
if count > 1 {
heap.push((count - 1, letter));
}
}
}
String::from_utf8(result).unwrap()
}
/** LC 1405. Greedy by largest remaining count, holding back any letter that would run three long. */
export function longestDiverseString(a: number, b: number, c: number): string {
const remaining: [number, string][] = [
[a, "a"],
[b, "b"],
[c, "c"],
];
const pieces: string[] = [];
for (;;) {
remaining.sort((x, y) => y[0] - x[0]); // three entries: re-sorting is the whole "max-heap"
let appended = false;
for (const entry of remaining) {
if (entry[0] === 0) break; // sorted descending, so nothing usable remains
const len = pieces.length;
if (len >= 2 && pieces[len - 1] === entry[1] && pieces[len - 2] === entry[1]) {
continue; // the best letter would form a triple: fall through to the second best
}
entry[0]--;
pieces.push(entry[1]);
appended = true;
break;
}
if (!appended) return pieces.join(""); // only a triple-forcing letter (or nothing) is left
}
}
// LC 1405. Max-heap by remaining count with a run cap of two: when the best
// letter would make a triple, take the runner-up and requeue the best.
func longestDiverseString(a int, b int, c int) string {
heap := [][2]int{} // (remaining count, letter)
higher := func(x, y [2]int) bool {
if x[0] != y[0] {
return x[0] > y[0]
}
return x[1] > y[1]
}
push := func(e [2]int) {
heap = append(heap, e)
for i := len(heap) - 1; i > 0; {
parent := (i - 1) / 2
if !higher(heap[i], heap[parent]) {
break
}
heap[i], heap[parent] = heap[parent], heap[i]
i = parent
}
}
pop := func() [2]int {
top := heap[0]
last := len(heap) - 1
heap[0] = heap[last]
heap = heap[:last]
for i := 0; ; {
next := i
if l := 2*i + 1; l < len(heap) && higher(heap[l], heap[next]) {
next = l
}
if r := 2*i + 2; r < len(heap) && higher(heap[r], heap[next]) {
next = r
}
if next == i {
break
}
heap[i], heap[next] = heap[next], heap[i]
i = next
}
return top
}
if a > 0 {
push([2]int{a, 'a'})
}
if b > 0 {
push([2]int{b, 'b'})
}
if c > 0 {
push([2]int{c, 'c'})
}
result := []byte{}
for len(heap) > 0 {
top := pop()
letter := byte(top[1])
if len(result) >= 2 && result[len(result)-1] == letter && result[len(result)-2] == letter {
if len(heap) == 0 {
break // only the triple-forcing letter remains
}
second := pop()
result = append(result, byte(second[1]))
if second[0] > 1 {
push([2]int{second[0] - 1, second[1]})
}
push(top) // best letter waits one slot, count unchanged
} else {
result = append(result, letter)
if top[0] > 1 {
push([2]int{top[0] - 1, top[1]})
}
}
}
return string(result)
}
// LC 1405. Same hold-back greedy with a run cap of two: when the best letter
// would make a triple, take the runner-up instead and requeue the best
// untouched; if only the triple-forcing letter remains, stop cleanly.
func longestDiverseString(_ a: Int, _ b: Int, _ c: Int) -> String {
var heap: [(Int, Character)] = [] // max-heap of (remaining count, letter)
func push(_ item: (Int, Character)) {
heap.append(item)
var child = heap.count - 1
while child > 0 {
let parent = (child - 1) / 2
if heap[parent] >= heap[child] { break }
heap.swapAt(parent, child)
child = parent
}
}
func pop() -> (Int, Character) {
let top = heap[0]
heap[0] = heap[heap.count - 1]
heap.removeLast()
var parent = 0
while true {
var largest = parent
let left = 2 * parent + 1
let right = 2 * parent + 2
if left < heap.count && heap[left] > heap[largest] { largest = left }
if right < heap.count && heap[right] > heap[largest] { largest = right }
if largest == parent { break }
heap.swapAt(parent, largest)
parent = largest
}
return top
}
if a > 0 { push((a, "a")) }
if b > 0 { push((b, "b")) }
if c > 0 { push((c, "c")) }
var result: [Character] = []
while !heap.isEmpty {
let (count, letter) = pop()
if result.count >= 2 && result[result.count - 1] == letter
&& result[result.count - 2] == letter {
if heap.isEmpty { break } // only the triple-forcing letter remains
let (secondCount, secondLetter) = pop()
result.append(secondLetter)
if secondCount > 1 { push((secondCount - 1, secondLetter)) }
push((count, letter)) // best letter waits one slot
} else {
result.append(letter)
if count > 1 { push((count - 1, letter)) }
}
}
return String(result)
}
10. Car Pooling
Medium · LC 1094
Given trips as passenger count, pickup, and dropoff locations plus a capacity, decide whether one car driving east can serve every trip without exceeding capacity. Build a difference array over stops, adding passengers at pickup and subtracting at dropoff, then prefix-sum and compare the running load against capacity. Locations are bounded by 1000, which makes the difference array tiny; a min-heap ordered by dropoff works when coordinates are large.
def car_pooling(trips: list[list[int]], capacity: int) -> bool:
"""LC 1094. Car Pooling.
Locations are bounded by 1000, so a difference array over the stops
beats a heap: add passengers at each pickup, subtract at each
dropoff, then prefix-sum and compare the running load against
capacity. Dropoffs land before pickups at the same stop for free,
because both deltas join the same cell before the sum. O(n + 1001)
time, O(1001) space.
"""
load_changes = [0] * 1001
for passengers, pickup, dropoff in trips:
load_changes[pickup] += passengers
load_changes[dropoff] -= passengers
riding = 0
for change in load_changes:
riding += change
if riding > capacity:
return False
return True
// LC 1094. Difference array over the bounded 0..1000 road: add passengers at
// pickup, subtract at dropoff, then prefix-sum and compare the running load
// against capacity. Dropoff is exclusive, so a dropoff and pickup at the same
// stop never overlap.
bool carPooling(vector<vector<int>> trips, int capacity) {
vector<int> delta(1001, 0);
for (const vector<int>& trip : trips) {
delta[trip[1]] += trip[0];
delta[trip[2]] -= trip[0]; // passengers leave before new ones board
}
int load = 0;
for (int change : delta) {
load += change;
if (load > capacity) return false;
}
return true;
}
/// LC 1094. Difference array over the 0..=1000 location range: add
/// passengers at pickup, subtract at dropoff, then prefix-sum and compare
/// the running load against capacity. Dropoffs at a stop free seats before
/// pickups there need them, which the +/- at the same index handles for free.
pub fn car_pooling(trips: Vec<Vec<i32>>, capacity: i32) -> bool {
let mut delta = [0i32; 1001];
for trip in &trips {
delta[trip[1] as usize] += trip[0];
delta[trip[2] as usize] -= trip[0];
}
let mut load = 0;
for change in delta {
load += change;
if load > capacity {
return false;
}
}
true
}
/** LC 1094. Difference array over the 0..1000 stops; prefix-sum the load and compare to capacity. */
export function carPooling(trips: number[][], capacity: number): boolean {
const delta = new Array<number>(1001).fill(0); // locations are bounded by 1000
for (const [passengers, from, to] of trips) {
delta[from] += passengers;
delta[to] -= passengers; // riders leave at `to`, freeing seats for pickups at that same stop
}
let load = 0;
for (const change of delta) {
load += change;
if (load > capacity) return false;
}
return true;
}
// LC 1094. Difference array over the bounded 0..1000 stops: board at pickup,
// leave at dropoff (exclusive), then prefix-sum the load against capacity.
func carPooling(trips [][]int, capacity int) bool {
delta := [1001]int{}
for _, trip := range trips {
delta[trip[1]] += trip[0]
delta[trip[2]] -= trip[0] // passengers leave before new ones board
}
load := 0
for _, change := range delta {
load += change
if load > capacity {
return false
}
}
return true
}
// LC 1094. Difference array over the bounded 0...1000 road: add passengers at
// pickup, subtract at dropoff, then prefix-sum the load against capacity.
func carPooling(_ trips: [[Int]], _ capacity: Int) -> Bool {
var delta = [Int](repeating: 0, count: 1001)
for trip in trips {
delta[trip[1]] += trip[0]
delta[trip[2]] -= trip[0] // passengers leave before new ones board
}
var load = 0
for change in delta {
load += change
if load > capacity { return false }
}
return true
}
11. Find Median From Data Stream
Hard · LC 295
Design a structure supporting addNum and findMedian over a stream of integers. Keep two heaps, a max-heap for the lower half and a min-heap for the upper half, rebalancing after every insert so the sizes differ by at most one. The invariant that every low-half element is at most every high-half element makes the median either the larger heap's root or the average of the two roots.
class MedianFinder:
"""LC 295. Find Median from Data Stream.
Two heaps split the stream: a max-heap (negated) for the lower half
and a min-heap for the upper half. Rebalance invariant: every low
element <= every high element, and len(low) equals len(high) or
exceeds it by exactly one. The median is then the low root alone or
the average of the two roots. O(log n) add, O(1) median.
"""
def __init__(self) -> None:
self._low: list[int] = [] # negated max-heap: the lower half
self._high: list[int] = [] # min-heap: the upper half
def add_num(self, num: int) -> None:
# route through low, then move low's max up: this keeps the ordering
# invariant no matter where num falls relative to the current median
heapq.heappush(self._low, -num)
heapq.heappush(self._high, -heapq.heappop(self._low))
if len(self._high) > len(self._low): # restore the size invariant
heapq.heappush(self._low, -heapq.heappop(self._high))
def find_median(self) -> float:
if len(self._low) > len(self._high):
return float(-self._low[0])
return (-self._low[0] + self._high[0]) / 2
// LC 295. Two heaps split the stream: a max-heap for the lower half and a
// min-heap for the upper half, rebalanced after every insert so sizes differ
// by at most one (lower may hold the extra). The median is the lower root or
// the average of the two roots.
class MedianFinder {
priority_queue<int> lowerHalf; // max-heap
priority_queue<int, vector<int>, greater<int>> upperHalf; // min-heap
public:
void addNum(int num) {
lowerHalf.push(num);
upperHalf.push(lowerHalf.top()); // route the lower maximum upward
lowerHalf.pop();
if (upperHalf.size() > lowerHalf.size()) { // lower half keeps the extra element
lowerHalf.push(upperHalf.top());
upperHalf.pop();
}
}
double findMedian() {
if (lowerHalf.size() > upperHalf.size()) return lowerHalf.top();
return (lowerHalf.top() + upperHalf.top()) / 2.0;
}
};
/// LC 295. Two heaps split the stream: a max-heap owns the lower half and
/// a Reverse min-heap owns the upper half, with lower allowed to be one
/// longer. Every insert routes through lower then promotes lower's max up,
/// rebalancing back if upper outgrows lower -- so the median is lower's
/// root, or the mean of the two roots on even counts.
pub struct MedianFinder {
lower: BinaryHeap<i32>,
upper: BinaryHeap<Reverse<i32>>,
}
impl MedianFinder {
pub fn new() -> Self {
MedianFinder { lower: BinaryHeap::new(), upper: BinaryHeap::new() }
}
pub fn add_num(&mut self, num: i32) {
// Route through lower and promote its max so every lower <= every upper.
self.lower.push(num);
let promoted = self.lower.pop().unwrap();
self.upper.push(Reverse(promoted));
if self.upper.len() > self.lower.len() {
let Reverse(demoted) = self.upper.pop().unwrap();
self.lower.push(demoted);
}
}
pub fn find_median(&self) -> f64 {
if self.lower.len() > self.upper.len() {
*self.lower.peek().unwrap() as f64
} else {
(*self.lower.peek().unwrap() as f64 + self.upper.peek().unwrap().0 as f64) / 2.0
}
}
}
/** LC 295. Two heaps split the stream; storing the lower half negated lets one min-heap serve both. */
export class MedianFinder {
private low: number[] = []; // lower half, negated: a min-heap acting as a max-heap
private high: number[] = []; // upper half: a plain min-heap
addNum(num: number): void {
// routing through low sends the largest of (low + num) to high, keeping every low <= every high
this.push(this.low, -num);
this.push(this.high, -this.pop(this.low));
if (this.high.length > this.low.length + 1) this.push(this.low, -this.pop(this.high));
}
findMedian(): number {
if (this.high.length > this.low.length) return this.high[0];
return (this.high[0] - this.low[0]) / 2; // -low[0] is the lower half's maximum
}
private push(heap: number[], val: number): void {
heap.push(val);
let child = heap.length - 1;
while (child > 0) {
const parent = (child - 1) >> 1;
if (heap[parent] <= heap[child]) break;
[heap[parent], heap[child]] = [heap[child], heap[parent]];
child = parent;
}
}
private pop(heap: number[]): number {
const top = heap[0];
const last = heap.pop()!;
if (heap.length > 0) {
heap[0] = last;
let parent = 0;
for (;;) {
let smallest = parent;
const left = 2 * parent + 1;
const right = 2 * parent + 2;
if (left < heap.length && heap[left] < heap[smallest]) smallest = left;
if (right < heap.length && heap[right] < heap[smallest]) smallest = right;
if (smallest === parent) break;
[heap[parent], heap[smallest]] = [heap[smallest], heap[parent]];
parent = smallest;
}
}
return top;
}
}
// LC 295. Two heaps split the stream: a negated max-heap for the lower half,
// a min-heap for the upper, rebalanced so the lower keeps the odd extra.
type MedianFinder struct {
low []int // negated max-heap: the lower half
high []int // min-heap: the upper half
}
func newMedianFinder() *MedianFinder {
return &MedianFinder{}
}
func (mf *MedianFinder) addNum(num int) {
push := func(h []int, v int) []int {
h = append(h, v)
for i := len(h) - 1; i > 0; {
parent := (i - 1) / 2
if h[parent] <= h[i] {
break
}
h[i], h[parent] = h[parent], h[i]
i = parent
}
return h
}
pop := func(h []int) ([]int, int) {
top := h[0]
last := len(h) - 1
h[0] = h[last]
h = h[:last]
for i := 0; ; {
next := i
if l := 2*i + 1; l < len(h) && h[l] < h[next] {
next = l
}
if r := 2*i + 2; r < len(h) && h[r] < h[next] {
next = r
}
if next == i {
break
}
h[i], h[next] = h[next], h[i]
i = next
}
return h, top
}
// route through low, then move low's max up: the ordering invariant
// holds no matter where num falls relative to the current median
var moved int
mf.low = push(mf.low, -num)
mf.low, moved = pop(mf.low)
mf.high = push(mf.high, -moved)
if len(mf.high) > len(mf.low) { // the lower half keeps the extra element
mf.high, moved = pop(mf.high)
mf.low = push(mf.low, -moved)
}
}
func (mf *MedianFinder) findMedian() float64 {
if len(mf.low) > len(mf.high) {
return float64(-mf.low[0])
}
return float64(-mf.low[0]+mf.high[0]) / 2
}
// LC 295. Two heaps split the stream: the lower half lives negated in a
// min-heap (acting as a max-heap), the upper half in a plain min-heap,
// rebalanced so the lower half keeps the extra element on odd counts.
class MedianFinder {
private var low: [Int] = [] // negated max-heap: the lower half
private var high: [Int] = [] // min-heap: the upper half
func addNum(_ num: Int) {
// route through low, then move low's max up: this keeps the ordering
// invariant no matter where num falls relative to the current median
push(&low, -num)
push(&high, -pop(&low))
if high.count > low.count { // restore the size invariant
push(&low, -pop(&high))
}
}
func findMedian() -> Double {
if low.count > high.count { return Double(-low[0]) }
return Double(-low[0] + high[0]) / 2.0
}
private func push(_ heap: inout [Int], _ val: Int) {
heap.append(val)
var child = heap.count - 1
while child > 0 {
let parent = (child - 1) / 2
if heap[parent] <= heap[child] { break }
heap.swapAt(parent, child)
child = parent
}
}
private func pop(_ heap: inout [Int]) -> Int {
let top = heap[0]
heap[0] = heap[heap.count - 1]
heap.removeLast()
var parent = 0
while true {
var smallest = parent
let left = 2 * parent + 1
let right = 2 * parent + 2
if left < heap.count && heap[left] < heap[smallest] { smallest = left }
if right < heap.count && heap[right] < heap[smallest] { smallest = right }
if smallest == parent { break }
heap.swapAt(parent, smallest)
parent = smallest
}
return top
}
}
12. IPO
Hard · LC 502
Given projects with capital requirements and profits, starting capital w, and at most k picks, maximize the final capital, where each finished project adds its profit. Sort projects by required capital, and in each of k rounds push all newly affordable profits into a max-heap and pop the largest. The greedy is safe because profit only grows capital and unlocks more options; stop early if the heap ever empties.
def find_maximized_capital(
k: int, w: int, profits: list[int], capital: list[int]
// LC 502. Sort projects by required capital; in each of k rounds push every
// newly affordable profit into a max-heap and take the largest. Greedy is
// safe because profit only grows capital and unlocks more options; stop early
// if nothing is affordable.
int findMaximizedCapital(int k, int w, vector<int> profits, vector<int> capital) {
int n = static_cast<int>(profits.size());
vector<int> byCapital(n);
iota(byCapital.begin(), byCapital.end(), 0);
sort(byCapital.begin(), byCapital.end(), [&](int a, int b) { return capital[a] < capital[b]; });
priority_queue<int> affordableProfits;
long long currentCapital = w;
int next = 0;
for (int round = 0; round < k; ++round) {
while (next < n && capital[byCapital[next]] <= currentCapital)
affordableProfits.push(profits[byCapital[next++]]);
if (affordableProfits.empty()) break; // nothing affordable, no project ever will be
currentCapital += affordableProfits.top();
affordableProfits.pop();
}
return static_cast<int>(currentCapital);
}
/// LC 502. Sort projects by required capital; in each of k rounds push
/// every newly affordable profit into a max-heap and take the largest.
/// The greedy is safe because profit only ever grows capital and unlocks
/// more projects. Stop early when nothing is affordable; track capital in
/// i64 since w + k * max_profit can overflow i32 mid-run.
pub fn find_maximized_capital(k: i32, w: i32, profits: Vec<i32>, capital: Vec<i32>) -> i32 {
let mut projects: Vec<(i32, i32)> = capital.into_iter().zip(profits).collect();
projects.sort_unstable();
let mut affordable: BinaryHeap<i32> = BinaryHeap::new();
let mut total = w as i64;
let mut next = 0;
for _ in 0..k {
while next < projects.len() && (projects[next].0 as i64) <= total {
affordable.push(projects[next].1);
next += 1;
}
match affordable.pop() {
None => break, // nothing affordable, and more capital is unreachable
Some(profit) => total += profit as i64,
}
}
total as i32
}
/** LC 502. Sort by required capital; each round, push newly affordable profits, pop the largest. */
export function findMaximizedCapital(k: number, w: number, profits: number[], capital: number[]): number {
const byCapital = profits.map((_, index) => index).sort((a, b) => capital[a] - capital[b]);
const heap: number[] = []; // max-heap of profits whose capital requirement is already met
const push = (val: number): void => {
heap.push(val);
let child = heap.length - 1;
while (child > 0) {
const parent = (child - 1) >> 1;
if (heap[parent] >= heap[child]) break;
[heap[parent], heap[child]] = [heap[child], heap[parent]];
child = parent;
}
};
const pop = (): number => {
const top = heap[0];
const last = heap.pop()!;
if (heap.length > 0) {
heap[0] = last;
let parent = 0;
for (;;) {
let largest = parent;
const left = 2 * parent + 1;
const right = 2 * parent + 2;
if (left < heap.length && heap[left] > heap[largest]) largest = left;
if (right < heap.length && heap[right] > heap[largest]) largest = right;
if (largest === parent) break;
[heap[parent], heap[largest]] = [heap[largest], heap[parent]];
parent = largest;
}
}
return top;
};
let next = 0; // next unprocessed position in byCapital
for (let round = 0; round < k; round++) {
while (next < byCapital.length && capital[byCapital[next]] <= w) push(profits[byCapital[next++]]);
if (heap.length === 0) break; // nothing affordable now means nothing ever will be
w += pop(); // profit only grows capital and unlocks more options, so the greedy pick is safe
}
return w;
}
// LC 502. Sort projects by required capital; each of k rounds unlocks every
// newly affordable profit into a max-heap and takes the largest.
func findMaximizedCapital(k int, w int, profits []int, capital []int) int {
n := len(profits)
byCapital := make([]int, n)
for i := range byCapital {
byCapital[i] = i
}
sort.Slice(byCapital, func(a, b int) bool {
return capital[byCapital[a]] < capital[byCapital[b]]
})
heap := []int{} // max-heap of unlocked profits
push := func(v int) {
heap = append(heap, v)
for i := len(heap) - 1; i > 0; {
parent := (i - 1) / 2
if heap[parent] >= heap[i] {
break
}
heap[i], heap[parent] = heap[parent], heap[i]
i = parent
}
}
pop := func() int {
top := heap[0]
last := len(heap) - 1
heap[0] = heap[last]
heap = heap[:last]
for i := 0; ; {
next := i
if l := 2*i + 1; l < len(heap) && heap[l] > heap[next] {
next = l
}
if r := 2*i + 2; r < len(heap) && heap[r] > heap[next] {
next = r
}
if next == i {
break
}
heap[i], heap[next] = heap[next], heap[i]
i = next
}
return top
}
currentCapital := w
next := 0
for round := 0; round < k; round++ {
for next < n && capital[byCapital[next]] <= currentCapital {
push(profits[byCapital[next]])
next++
}
if len(heap) == 0 {
break // nothing affordable now, and capital only grows by taking projects
}
currentCapital += pop()
}
return currentCapital
}
// LC 502. Sort projects by required capital; each round unlock every newly
// affordable profit into a max-heap and take the largest -- profit only grows
// capital, so the greedy never closes a future door.
func findMaximizedCapital(_ k: Int, _ w: Int, _ profits: [Int], _ capital: [Int]) -> Int {
var heap: [Int] = [] // max-heap of unlocked profits
func push(_ val: Int) {
heap.append(val)
var child = heap.count - 1
while child > 0 {
let parent = (child - 1) / 2
if heap[parent] >= heap[child] { break }
heap.swapAt(parent, child)
child = parent
}
}
func pop() -> Int {
let top = heap[0]
heap[0] = heap[heap.count - 1]
heap.removeLast()
var parent = 0
while true {
var largest = parent
let left = 2 * parent + 1
let right = 2 * parent + 2
if left < heap.count && heap[left] > heap[largest] { largest = left }
if right < heap.count && heap[right] > heap[largest] { largest = right }
if largest == parent { break }
heap.swapAt(parent, largest)
parent = largest
}
return top
}
let byCapital = profits.indices.sorted { capital[$0] < capital[$1] }
var currentCapital = w
var next = 0
for _ in 0..<k {
while next < byCapital.count && capital[byCapital[next]] <= currentCapital {
push(profits[byCapital[next]])
next += 1
}
if heap.isEmpty { break } // nothing affordable, and nothing ever will be
currentCapital += pop()
}
return currentCapital
}