Smallest Range Covering Elements from K Lists

This page explains Java solution to problem Smallest Range Covering Elements from K Lists using Priority Queue data structure.

Problem Statement

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.

Example 1:

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output: [20,24]
Explanation: List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Example 2:

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

Example 3:

Input: nums = [[10,10],[11,11]]
Output: [10,11]

Example 4:

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

Solution

If you have any suggestions in below code, please create a pull request by clicking here.

package com.vc.hard;

import java.util.*;

class SmallestRangeCoveringElementsFromKLists {
    public int[] smallestRange(List<List<Integer>> nums) {
        if(nums == null || nums.size() == 0) return new int[0];

        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>(){
            public int compare(int[] x, int[] y) {
                return Integer.compare(x[2], y[2]);
            }
        });

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < nums.size(); i++) {
            int val = nums.get(i).get(0);
            pq.offer(new int[]{i, 0, val});
            min = Math.min(min, val);
            max = Math.max(max, val);
        }

        int start = min;
        int end = max;
        int minRange = end - start;
        while(pq.size() == nums.size()) {
            int[] q = pq.poll();
            int row = q[0];
            int col = q[1];
            int val = q[2];

            if(max - val < minRange) {
                minRange = max - val;
                min = val;
                start = min;
                end = max;
            }

            if(col + 1 < nums.get(row).size()) {
                int newVal = nums.get(row).get(col + 1);
                pq.offer(new int[]{row, col + 1, newVal});
                max = Math.max(max, newVal);
            }
        }

        return new int[]{start, end};
    }
}

Time Complexity

O(N * Log K) Where
K is size of nums
N is max of (nums[0].size(), nums[1].size() .... nums[k].size())

Space Complexity

O(K) Where
K is length of nums
N is max of (nums[0].size(), nums[1].size() .... nums[k].size())