Table of Contents

# Smallest Range Covering Elements from K Lists – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

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.

We define the range `[a, b]`

is smaller than range `[c, d]`

if `b - a < d - c`

**or** `a < c`

if `b - a == d - c`

.

**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]

**Constraints:**

`nums.length == k`

`1 <= k <= 3500`

`1 <= nums[i].length <= 50`

`-10`

^{5}<= nums[i][j] <= 10^{5}`nums[i]`

is sorted in**non-decreasing**order.

# C++ Smallest Range Covering Elements from K Lists LeetCode Solution

```
``````
class Solution {
public:
class node{
public:
int data;
int row;
int col;
node(int d,int r,int c){
this->data=d;
this->row = r;
this->col = c;
}
};
class compare{
public:
bool operator()(node*a,node*b){return a->data > b->data;}
};
vector<int> smallestRange(vector<vector<int>>& nums) {
vector<int>ans;
if(nums.size()==0)return ans;
priority_queue<node*,vector<node*>,compare> hp;
int mini = INT_MAX, maxi = INT_MIN;
int k = nums.size();
//storing first value.
for(int i = 0;i<k;i++){
int ele = nums[i][0];
maxi = max(maxi,ele);
mini = min(mini,ele);
hp.push(new node (ele,i,0));
}
int st = mini, end = maxi;
while(!hp.empty()){
node * temp = hp.top();
hp.pop();
mini = temp->data;
if(maxi - mini < end - st){
st = mini;
end = maxi;
}
//add new value to heap and updating maxi also
if(temp->col +1 < nums[temp->row].size()){
maxi = max(maxi,nums[temp->row][temp->col+1]);
hp.push(new node(nums[temp->row][temp->col+1],temp->row,temp->col+1));
}
else break;
}
ans.push_back(st);
ans.push_back(end);
return ans;
}
};
```

# Java Smallest Range Covering Elements from K Lists LeetCode Solution

```
``````
class Solution {
class Node{
int arrNo;
int index;
int value;
public Node(int arrNo, int index, int value){
this.arrNo = arrNo;
this.index = index;
this.value = value;
}
}
public int[] smallestRange(List<List<Integer>> nums) {
//it seems as though there will never be a point where we will remove the current biggest
//and the next biggest is within the minheap and not the next one added
int max = Integer.MIN_VALUE;
//Add all the first numbers into the priority queue
PriorityQueue<Node> minheap = new PriorityQueue<>((n1,n2)->n1.value-n2.value);
for(int i = 0; i < nums.size(); i++){
List<Integer> num = nums.get(i);
minheap.add(new Node(i, 0, num.get(0)));
max = Math.max(max, num.get(0));
}
int min = minheap.peek().value;
int[] ans = new int[]{min, max};
int range = max - min;
//we will then iterate through and update ans accordingly if range is smaller than past ranges
//Note that the next node can still be the smallest.
Node nextNode = minheap.poll();
while(nextNode.index + 1 < nums.get(nextNode.arrNo).size()){
int nextArr = nextNode.arrNo;
int nextIndex = nextNode.index + 1;
Node newNode = new Node(nextArr, nextIndex, nums.get(nextArr).get(nextIndex));
//add the new Node and check the range changes
minheap.offer(newNode);
max = Math.max(max, newNode.value);
min = minheap.peek().value;
if(range > max-min){
range = max - min;
ans = new int[]{min, max};
}
nextNode = minheap.poll();
}
return ans;
}
}
```

# Python 3 Smallest Range Covering Elements from K Lists LeetCode Solution

```
``````
from heapq import heappush, heappop
class Solution:
def smallestRange(self, nums: List[List[int]]) -> List[int]:
n = len(nums)
next_idx = [0]*n
# cur_val, next_idx, sublist_idx
min_idx_pq = []
cur_min = float('inf')
cur_max = float('-inf')
for i in range(n):
heappush(min_idx_pq, (nums[i][0],0,i))
cur_min = min(cur_min,nums[i][0])
cur_max = max(cur_max,nums[i][0])
smallest_interval = [cur_min,cur_max]
smallest_interval_len = cur_max - cur_min
while True:
cur_val, next_idx, sublist_idx = heappop(min_idx_pq)
next_idx += 1
if next_idx == len(nums[sublist_idx]):
break
cur_val = nums[sublist_idx][next_idx]
heappush(min_idx_pq,(cur_val,next_idx,sublist_idx))
cur_min = min_idx_pq[0][0]
cur_max = max(cur_max,cur_val)
cur_interval = cur_max - cur_min
if cur_interval < smallest_interval_len:
smallest_interval_len = cur_interval
smallest_interval = [cur_min,cur_max]
return smallest_interval
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1