LC-0632 Hard LeetCode

632. Smallest Range Covering Elements from K Lists

Array Hash Table Greedy Sliding Window Sorting Heap (Priority Queue)

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 70% Topics: Array, Hash Table, Greedy, Sliding Window, Sorting, Heap (Priority Queue)

View full problem on LeetCode

Also on leetcode.ca (community mirror)

Reading material

Arrays & Hashing 12 min Greedy 11 min Sliding Window 11 min

Reference solution (spoiler · java)

import java.util.*;

class Solution {
    int[] smallestRange(int[][] nums) {
        int k = nums.length;
        // heap of [value, listIdx, elemIdx]
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        int curMax = Integer.MIN_VALUE;
        for (int i = 0; i < k; i++) {
            pq.offer(new int[]{nums[i][0], i, 0});
            curMax = Math.max(curMax, nums[i][0]);
        }
        int bestLo = pq.peek()[0], bestHi = curMax;
        while (true) {
            int[] top = pq.poll();
            int lo = top[0];
            if (curMax - lo < bestHi - bestLo) {
                bestLo = lo;
                bestHi = curMax;
            }
            int li = top[1], ei = top[2];
            if (ei + 1 == nums[li].length) break;
            int nv = nums[li][ei + 1];
            curMax = Math.max(curMax, nv);
            pq.offer(new int[]{nv, li, ei + 1});
        }
        return new int[]{bestLo, bestHi};
    }
}

Solution from kamyu104/LeetCode-Solutions · MIT