# 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())