177. Shortest Stretch Reaching K
A shop keeps a daily profit log in the array nums; a day can end in a loss, so entries may be negative. The owner wants a short, unbroken run of days whose total profit is at least k.
Return the length of the shortest non-empty run of consecutive days whose sum is greater than or equal to k. If no such run exists, return -1. Because negative days can both help and hurt, a simple window that only grows and shrinks from one side is not enough here. Totals can exceed 32 bits, so use a wider type internally.
Example 1
- Input:
- nums = [2,-1,2], k = 3
- Output:
- 3
- Explanation:
Only the whole array reaches 3 (2 - 1 + 2), so the shortest run has length 3.
Example 2
- Input:
- nums = [1,2], k = 4
- Output:
- -1
- Explanation:
The best total is 1 + 2 = 3, which is less than 4, so the answer is -1.
Example 3
- Input:
- nums = [3,-2,5,-1,4], k = 6
- Output:
- 3
- Explanation:
No run of length 1 or 2 reaches 6, but 3 - 2 + 5 = 6 does, so the shortest run has length 3.
Constraints
1 ≤ nums.length ≤ 105
-105 ≤ nums[i] ≤ 105
1 ≤ k ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)