Greedy
Array
Hash Table
Sorting
Sliding Window
Heap (Priority Queue)
Description
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
-105 <= nums[i][j] <= 105
nums[i]
is sorted in non-decreasing order.
Solutions
Solution 1
Python3 Java C++ Go Rust
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 class Solution :
def smallestRange ( self , nums : List [ List [ int ]]) -> List [ int ]:
t = [( x , i ) for i , v in enumerate ( nums ) for x in v ]
t . sort ()
cnt = Counter ()
ans = [ - inf , inf ]
j = 0
for i , ( b , v ) in enumerate ( t ):
cnt [ v ] += 1
while len ( cnt ) == len ( nums ):
a = t [ j ][ 0 ]
x = b - a - ( ans [ 1 ] - ans [ 0 ])
if x < 0 or ( x == 0 and a < ans [ 0 ]):
ans = [ a , b ]
w = t [ j ][ 1 ]
cnt [ w ] -= 1
if cnt [ w ] == 0 :
cnt . pop ( w )
j += 1
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 class Solution {
public int [] smallestRange ( List < List < Integer >> nums ) {
int n = 0 ;
for ( var v : nums ) {
n += v . size ();
}
int [][] t = new int [ n ][ 2 ] ;
int k = nums . size ();
for ( int i = 0 , j = 0 ; i < k ; ++ i ) {
for ( int x : nums . get ( i )) {
t [ j ++] = new int [] { x , i };
}
}
Arrays . sort ( t , ( a , b ) -> a [ 0 ] - b [ 0 ] );
int j = 0 ;
Map < Integer , Integer > cnt = new HashMap <> ();
int [] ans = new int [] { - 1000000 , 1000000 };
for ( int [] e : t ) {
int b = e [ 0 ] ;
int v = e [ 1 ] ;
cnt . put ( v , cnt . getOrDefault ( v , 0 ) + 1 );
while ( cnt . size () == k ) {
int a = t [ j ][ 0 ] ;
int w = t [ j ][ 1 ] ;
int x = b - a - ( ans [ 1 ] - ans [ 0 ] );
if ( x < 0 || ( x == 0 && a < ans [ 0 ] )) {
ans [ 0 ] = a ;
ans [ 1 ] = b ;
}
cnt . put ( w , cnt . get ( w ) - 1 );
if ( cnt . get ( w ) == 0 ) {
cnt . remove ( w );
}
++ j ;
}
}
return ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 class Solution {
public :
vector < int > smallestRange ( vector < vector < int >>& nums ) {
int n = 0 ;
for ( auto & v : nums ) n += v . size ();
vector < pair < int , int >> t ( n );
int k = nums . size ();
for ( int i = 0 , j = 0 ; i < k ; ++ i ) {
for ( int v : nums [ i ]) {
t [ j ++ ] = { v , i };
}
}
sort ( t . begin (), t . end ());
int j = 0 ;
unordered_map < int , int > cnt ;
vector < int > ans = { -1000000 , 1000000 };
for ( int i = 0 ; i < n ; ++ i ) {
int b = t [ i ]. first ;
int v = t [ i ]. second ;
++ cnt [ v ];
while ( cnt . size () == k ) {
int a = t [ j ]. first ;
int w = t [ j ]. second ;
int x = b - a - ( ans [ 1 ] - ans [ 0 ]);
if ( x < 0 || ( x == 0 && a < ans [ 0 ])) {
ans [ 0 ] = a ;
ans [ 1 ] = b ;
}
if ( -- cnt [ w ] == 0 ) {
cnt . erase ( w );
}
++ j ;
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 func smallestRange ( nums [][] int ) [] int {
t := [][] int {}
for i , x := range nums {
for _ , v := range x {
t = append ( t , [] int { v , i })
}
}
sort . Slice ( t , func ( i , j int ) bool { return t [ i ][ 0 ] < t [ j ][ 0 ] })
ans := [] int { - 1000000 , 1000000 }
j := 0
cnt := map [ int ] int {}
for _ , x := range t {
b , v := x [ 0 ], x [ 1 ]
cnt [ v ] ++
for len ( cnt ) == len ( nums ) {
a , w := t [ j ][ 0 ], t [ j ][ 1 ]
x := b - a - ( ans [ 1 ] - ans [ 0 ])
if x < 0 || ( x == 0 && a < ans [ 0 ]) {
ans [ 0 ], ans [ 1 ] = a , b
}
cnt [ w ] --
if cnt [ w ] == 0 {
delete ( cnt , w )
}
j ++
}
}
return ans
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 impl Solution {
pub fn smallest_range ( nums : Vec < Vec < i32 >> ) -> Vec < i32 > {
let mut t = vec! [];
for ( i , x ) in nums . iter (). enumerate () {
for & v in x {
t . push (( v , i ));
}
}
t . sort_unstable ();
let ( mut ans , n ) = ( vec! [ - 1000000 , 1000000 ], nums . len ());
let mut j = 0 ;
let mut cnt = std :: collections :: HashMap :: new ();
for ( b , v ) in t . iter () {
let ( b , v ) = ( * b , * v );
if let Some ( x ) = cnt . get_mut ( & v ) {
* x += 1 ;
} else {
cnt . insert ( v , 1 );
}
while cnt . len () == n {
let ( a , w ) = t [ j ];
let x = b - a - ( ans [ 1 ] - ans [ 0 ]);
if x < 0 || ( x == 0 && a < ans [ 0 ]) {
ans = vec! [ a , b ];
}
if let Some ( x ) = cnt . get_mut ( & w ) {
* x -= 1 ;
}
if cnt [ & w ] == 0 {
cnt . remove ( & w );
}
j += 1 ;
}
}
ans
}
}
Solution 2: Priority Queue (Heap)
TypeScript JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 const smallestRange = ( nums : number [][]) : number [] => {
const pq = new MinPriorityQueue < [ number , number , number ] > ({ priority : ([ x ]) => x });
const n = nums . length ;
let [ l , r , max ] = [ 0 , Number . POSITIVE_INFINITY , Number . NEGATIVE_INFINITY ];
for ( let j = 0 ; j < n ; j ++ ) {
const x = nums [ j ][ 0 ];
pq . enqueue ([ x , j , 0 ]);
max = Math . max ( max , x );
}
while ( pq . size () === n ) {
const [ min , j , i ] = pq . dequeue (). element ;
if ( max - min < r - l ) {
[ l , r ] = [ min , max ];
}
const iNext = i + 1 ;
if ( iNext < nums [ j ]. length ) {
const next = nums [ j ][ iNext ];
pq . enqueue ([ next , j , iNext ]);
max = Math . max ( max , next );
}
}
return [ l , r ];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 const smallestRange = nums => {
const pq = new MinPriorityQueue ({ priority : ([ x ]) => x });
const n = nums . length ;
let [ l , r , max ] = [ 0 , Number . POSITIVE_INFINITY , Number . NEGATIVE_INFINITY ];
for ( let j = 0 ; j < n ; j ++ ) {
const x = nums [ j ][ 0 ];
pq . enqueue ([ x , j , 0 ]);
max = Math . max ( max , x );
}
while ( pq . size () === n ) {
const [ min , j , i ] = pq . dequeue (). element ;
if ( max - min < r - l ) {
[ l , r ] = [ min , max ];
}
const iNext = i + 1 ;
if ( iNext < nums [ j ]. length ) {
const next = nums [ j ][ iNext ];
pq . enqueue ([ next , j , iNext ]);
max = Math . max ( max , next );
}
}
return [ l , r ];
};