LeetCode 632: Smallest Range Covering Elements from K Lists Solution

Master LeetCode problem 632 (Smallest Range Covering Elements from K Lists), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

632. Smallest Range Covering Elements from K Lists

Hard

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

Problem Explanation

Explanation:

To find the smallest range covering elements from k lists, we can use a sliding window approach. We start by initializing a priority queue to store the current minimum value and its corresponding list index. We then iterate through all the lists simultaneously, maintaining the maximum value among the current elements in the sliding window. At each step, we update the minimum range that covers at least one element from each list. By adjusting the sliding window based on the minimum and maximum values encountered, we can find the smallest range that satisfies the condition.

Algorithmic Idea:

Initialize a priority queue to store the current minimum value and its list index.
Initialize a variable to store the maximum value encountered so far.
Initialize a hashmap to keep track of the count of elements from each list that are included in the current range.
Iterate through all lists simultaneously and update the sliding window based on the minimum and maximum values.
Update the minimum range that covers at least one element from each list.
Repeat until all lists are exhausted.

Time Complexity:

The time complexity of this approach is O(nlogk), where n is the total number of elements across all lists and k is the number of lists.

Space Complexity:

The space complexity of this approach is O(k), where k is the number of lists.

Solution Code

class Solution {
    public int[] smallestRange(List<List<Integer>> nums) {
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int max = Integer.MIN_VALUE;
        int rangeStart = 0, rangeEnd = Integer.MAX_VALUE;

        for (int i = 0; i < nums.size(); i++) {
            minHeap.offer(new int[]{nums.get(i).get(0), i, 0});
            max = Math.max(max, nums.get(i).get(0));
        }

        while (minHeap.size() == nums.size()) {
            int[] curr = minHeap.poll();
            int currVal = curr[0], listIdx = curr[1], elemIdx = curr[2];

            if (max - currVal < rangeEnd - rangeStart) {
                rangeStart = currVal;
                rangeEnd = max;
            }

            if (elemIdx + 1 < nums.get(listIdx).size()) {
                int nextVal = nums.get(listIdx).get(elemIdx + 1);
                minHeap.offer(new int[]{nextVal, listIdx, elemIdx + 1});
                max = Math.max(max, nextVal);
            }
        }

        return new int[]{rangeStart, rangeEnd};
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 632 (Smallest Range Covering Elements from K Lists)?

This page provides optimized solutions for LeetCode problem 632 (Smallest Range Covering Elements from K Lists) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 632 (Smallest Range Covering Elements from K Lists)?

The time complexity for LeetCode 632 (Smallest Range Covering Elements from K Lists) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 632 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 632 in Java, C++, or Python.

Back to LeetCode Solutions