Skills101
← All coding problems

Shortest Subarray With Sum at Least K

hardArrays & Prefix Sums+40 XPTime limit 2s

Find the length of the shortest non-empty contiguous subarray whose sum is at least k. The array may contain negative numbers, so a simple sliding window does not work.

Input:

  • line 1: n k
  • line 2: n integers

Output: the shortest length, or -1 if no subarray reaches k.

Constraints: 1 ≤ n ≤ 10⁵, −10⁵ ≤ a[i] ≤ 10⁵, 1 ≤ k ≤ 10⁹.

Think about it: with prefix sums, you want j > i with P[j] − P[i] ≥ k and j − i small. Keep a deque of indices with increasing prefix sums. For each new j: pop from the front while P[j] − P[front] ≥ k (each popped start has found its best end); then pop from the back every index whose prefix is ≥ P[j] — a later, smaller start is always better.

Sample input 1

3 3
2 -1 2

Sample output 1

3

Sample input 2

2 4
1 2

Sample output 2

-1

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.