Minimum Cost Subarray with Sum at Least K
HardPractice library · +30 XPsliding windowprefix sumsmonotonic queue
Given an array A of N integers and an integer K, find the length of the shortest contiguous subarray whose sum is at least K. If no such subarray exists, return -1.
Input
The first line contains two integers N and K. The second line contains N space-separated integers representing the array A.
Output
Print a single integer: the length of the shortest subarray with sum at least K, or -1 if none exists.
Constraints
1 <= N <= 200000 1 <= K <= 10^15 -10^9 <= A[i] <= 10^9
Time limit 2 s (native code; slower languages get more)Memory 256 MB16 hidden tests
Example 1
Input
3 4 2 3 -1
Output
2
The subarray [2, 3] has sum 5 >= 4 and length 2, which is the shortest.
Example 2
Input
5 7 1 1 1 1 1
Output
-1
The shortest subarray with sum at least 7 does not exist. The total sum is 5.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
3 4 2 3 -1
Example 2 input
5 7 1 1 1 1 1