Queue
Array
Binary Search
Prefix Sum
Sliding Window
Monotonic Queue
Heap (Priority Queue)
Description
Given an integer array nums
and an integer k
, return the length of the shortest non-empty subarray of nums
with a sum of at least k
. If there is no such subarray , return -1
.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1], k = 1
Output: 1
Example 2:
Input: nums = [1,2], k = 4
Output: -1
Example 3:
Input: nums = [2,-1,2], k = 3
Output: 3
Constraints:
1 <= nums.length <= 105
-105 <= nums[i] <= 105
1 <= k <= 109
Solutions
Solution 1
Python3 Java C++ Go TypeScript JavaScript
1
2
3
4
5
6
7
8
9
10
11
12 class Solution :
def shortestSubarray ( self , nums : List [ int ], k : int ) -> int :
s = list ( accumulate ( nums , initial = 0 ))
q = deque ()
ans = inf
for i , v in enumerate ( s ):
while q and v - s [ q [ 0 ]] >= k :
ans = min ( ans , i - q . popleft ())
while q and s [ q [ - 1 ]] >= v :
q . pop ()
q . append ( i )
return - 1 if ans == inf else ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution {
public int shortestSubarray ( int [] nums , int k ) {
int n = nums . length ;
long [] s = new long [ n + 1 ] ;
for ( int i = 0 ; i < n ; ++ i ) {
s [ i + 1 ] = s [ i ] + nums [ i ] ;
}
Deque < Integer > q = new ArrayDeque <> ();
int ans = n + 1 ;
for ( int i = 0 ; i <= n ; ++ i ) {
while ( ! q . isEmpty () && s [ i ] - s [ q . peek () ] >= k ) {
ans = Math . min ( ans , i - q . poll ());
}
while ( ! q . isEmpty () && s [ q . peekLast () ] >= s [ i ] ) {
q . pollLast ();
}
q . offer ( i );
}
return ans > n ? - 1 : ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 class Solution {
public :
int shortestSubarray ( vector < int >& nums , int k ) {
int n = nums . size ();
vector < long > s ( n + 1 );
for ( int i = 0 ; i < n ; ++ i ) s [ i + 1 ] = s [ i ] + nums [ i ];
deque < int > q ;
int ans = n + 1 ;
for ( int i = 0 ; i <= n ; ++ i ) {
while ( ! q . empty () && s [ i ] - s [ q . front ()] >= k ) {
ans = min ( ans , i - q . front ());
q . pop_front ();
}
while ( ! q . empty () && s [ q . back ()] >= s [ i ]) q . pop_back ();
q . push_back ( i );
}
return ans > n ? -1 : ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 func shortestSubarray ( nums [] int , k int ) int {
n := len ( nums )
s := make ([] int , n + 1 )
for i , x := range nums {
s [ i + 1 ] = s [ i ] + x
}
q := [] int {}
ans := n + 1
for i , v := range s {
for len ( q ) > 0 && v - s [ q [ 0 ]] >= k {
ans = min ( ans , i - q [ 0 ])
q = q [ 1 :]
}
for len ( q ) > 0 && s [ q [ len ( q ) - 1 ]] >= v {
q = q [: len ( q ) - 1 ]
}
q = append ( q , i )
}
if ans > n {
return - 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 function shortestSubarray ( nums : number [], k : number ) : number {
const [ n , MAX ] = [ nums . length , Number . POSITIVE_INFINITY ];
const s = Array ( n + 1 ). fill ( 0 );
const q : number [] = [];
let ans = MAX ;
for ( let i = 0 ; i < n ; i ++ ) {
s [ i + 1 ] = s [ i ] + nums [ i ];
}
for ( let i = 0 ; i < n + 1 ; i ++ ) {
while ( q . length && s [ i ] - s [ q [ 0 ]] >= k ) {
ans = Math . min ( ans , i - q . shift () ! );
}
while ( q . length && s [ i ] <= s [ q . at ( - 1 ) ! ]) {
q . pop ();
}
q . push ( i );
}
return ans === MAX ? - 1 : 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 function shortestSubarray ( nums , k ) {
const [ n , MAX ] = [ nums . length , Number . POSITIVE_INFINITY ];
const s = Array ( n + 1 ). fill ( 0 );
const q = [];
let ans = MAX ;
for ( let i = 0 ; i < n ; i ++ ) {
s [ i + 1 ] = s [ i ] + nums [ i ];
}
for ( let i = 0 ; i < n + 1 ; i ++ ) {
while ( q . length && s [ i ] - s [ q [ 0 ]] >= k ) {
ans = Math . min ( ans , i - q . shift ());
}
while ( q . length && s [ i ] <= s [ q . at ( - 1 )]) {
q . pop ();
}
q . push ( i );
}
return ans === MAX ? - 1 : ans ;
}
GitHub