Smallest Range Covering Elements from K Lists

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        // [value, row, indexInRow] ordered by smallest value.
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int currentMax = Integer.MIN_VALUE;

        // Seed heap with the first value from each list.
        for (int row = 0; row < nums.size(); row++) {
            int value = nums.get(row).get(0);
            minHeap.offer(new int[] { value, row, 0 });
            currentMax = Math.max(currentMax, value);
        }

        int bestLeft = 0;
        int bestRight = Integer.MAX_VALUE;

        // Keep one active element from every list.
        while (minHeap.size() == nums.size()) {
            int[] top = minHeap.poll();
            int value = top[0], row = top[1], col = top[2];

            // Candidate range is [current min, current max].
            if (currentMax - value < bestRight - bestLeft ||
                (currentMax - value == bestRight - bestLeft && value < bestLeft)) {
                bestLeft = value;
                bestRight = currentMax;
            }

            // Cannot continue when one list is exhausted.
            if (col + 1 == nums.get(row).size()) {
                break;
            }

            int nextValue = nums.get(row).get(col + 1);
            minHeap.offer(new int[] { nextValue, row, col + 1 });
            currentMax = Math.max(currentMax, nextValue);
        }

        return new int[] { bestLeft, bestRight };
    }
}

type item struct {
    val, row, col int
}

type minHeap []item

func (h minHeap) Len() int           { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].val < h[j].val }
func (h minHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x any)       { *h = append(*h, x.(item)) }
func (h *minHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func smallestRange(nums [][]int) []int {
    h := &minHeap{}
    currentMax := nums[0][0]

    // Seed heap with first element from each list.
    for row := 0; row < len(nums); row++ {
        v := nums[row][0]
        if v > currentMax {
            currentMax = v
        }
        heap.Push(h, item{val: v, row: row, col: 0})
    }

    bestLeft, bestRight := 0, math.MaxInt32

    // Keep one active element from every list.
    for h.Len() == len(nums) {
        top := heap.Pop(h).(item)
        if currentMax-top.val < bestRight-bestLeft ||
            (currentMax-top.val == bestRight-bestLeft && top.val < bestLeft) {
            bestLeft, bestRight = top.val, currentMax
        }

        if top.col+1 == len(nums[top.row]) {
            break
        }

        nextVal := nums[top.row][top.col+1]
        heap.Push(h, item{val: nextVal, row: top.row, col: top.col + 1})
        if nextVal > currentMax {
            currentMax = nextVal
        }
    }

    return []int{bestLeft, bestRight}
}

class Solution:
    def smallestRange(self, nums: List[List[int]]) -> List[int]:
        heap = []
        current_max = float('-inf')

        # Seed heap with first element from each list.
        for row, arr in enumerate(nums):
            value = arr[0]
            heapq.heappush(heap, (value, row, 0))
            current_max = max(current_max, value)

        best_left, best_right = 0, float('inf')

        # Keep one active element from every list.
        while len(heap) == len(nums):
            value, row, col = heapq.heappop(heap)

            if (current_max - value < best_right - best_left) or (
                current_max - value == best_right - best_left and value < best_left
            ):
                best_left, best_right = value, current_max

            if col + 1 == len(nums[row]):
                break

            next_value = nums[row][col + 1]
            heapq.heappush(heap, (next_value, row, col + 1))
            current_max = max(current_max, next_value)

        return [best_left, best_right]

use std::cmp::Reverse;
use std::collections::BinaryHeap;

impl Solution {
    pub fn smallest_range(nums: Vec<Vec<i32>>) -> Vec<i32> {
        // Min-heap via Reverse(value, row, col).
        let mut heap: BinaryHeap<Reverse<(i32, usize, usize)>> = BinaryHeap::new();
        let mut current_max = i32::MIN;

        // Seed heap with first element from each list.
        for (row, arr) in nums.iter().enumerate() {
            let value = arr[0];
            heap.push(Reverse((value, row, 0)));
            if value > current_max {
                current_max = value;
            }
        }

        let mut best_left = 0;
        let mut best_right = i32::MAX;

        // Keep one active element from every list.
        while heap.len() == nums.len() {
            let Reverse((value, row, col)) = heap.pop().unwrap();

            if current_max - value < best_right - best_left
                || (current_max - value == best_right - best_left && value < best_left)
            {
                best_left = value;
                best_right = current_max;
            }

            if col + 1 == nums[row].len() {
                break;
            }

            let next_value = nums[row][col + 1];
            heap.push(Reverse((next_value, row, col + 1)));
            if next_value > current_max {
                current_max = next_value;
            }
        }

        vec![best_left, best_right]
    }
}

type Node = [number, number, number]; // [value, row, col]

class MinHeap {
  private data: Node[] = [];

  size(): number { return this.data.length; }

  push(x: Node): void {
    this.data.push(x);
    this.siftUp(this.data.length - 1);
  }

  pop(): Node {
    const root = this.data[0];
    const last = this.data.pop()!;
    if (this.data.length) {
      this.data[0] = last;
      this.siftDown(0);
    }
    return root;
  }

  private siftUp(i: number): void {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.data[p][0] <= this.data[i][0]) break;
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
      i = p;
    }
  }

  private siftDown(i: number): void {
    const n = this.data.length;
    while (true) {
      let m = i;
      const l = i * 2 + 1;
      const r = i * 2 + 2;
      if (l < n && this.data[l][0] < this.data[m][0]) m = l;
      if (r < n && this.data[r][0] < this.data[m][0]) m = r;
      if (m === i) break;
      [this.data[i], this.data[m]] = [this.data[m], this.data[i]];
      i = m;
    }
  }
}

function smallestRange(nums: number[][]): number[] {
  const heap = new MinHeap();
  let currentMax = -Infinity;

  // Seed heap with first element from each list.
  for (let row = 0; row < nums.length; row++) {
    const value = nums[row][0];
    heap.push([value, row, 0]);
    currentMax = Math.max(currentMax, value);
  }

  let bestLeft = 0;
  let bestRight = Infinity;

  // Keep one active element from every list.
  while (heap.size() === nums.length) {
    const [value, row, col] = heap.pop();

    if (
      currentMax - value < bestRight - bestLeft ||
      (currentMax - value === bestRight - bestLeft && value < bestLeft)
    ) {
      bestLeft = value;
      bestRight = currentMax;
    }

    if (col + 1 === nums[row].length) break;

    const nextValue = nums[row][col + 1];
    heap.push([nextValue, row, col + 1]);
    currentMax = Math.max(currentMax, nextValue);
  }

  return [bestLeft, bestRight];
}