Shortest Stretch Reaching a Target (With Refunds)
Daily balance changes nums may be negative (refunds). Return the length of the shortest non-empty contiguous subarray whose sum is at least target, or -1 if no such subarray exists.
Because values can be negative, the usual shrinking window does not work directly.
Example 1
Input: nums = [2, -1, 2], target = 3 Output: 3
Example 2
Input: nums = [5, -10, 3, 4], target = 6 Output: 2 Explanation: [3, 4] sums to 7.
Constraints
- 1 <= nums.length <= 10^5
- -10^5 <= nums[i] <= 10^5
- 1 <= target <= 10^9
Hint 1
Work with prefix sums: you need the closest i < j with pre[j] - pre[i] >= target.
Hint 2
Keep a deque of indices with increasing prefix sums. Pop from the front while the target is reached, and from the back while the new prefix is not larger.
Discussion 0
Join free to post in the discussion.
Good practice for: Data Scientist, Data Engineer, Machine Learning Engineer, AI Engineer (LLM & Generative AI), Backend Developer, Site Reliability Engineer
Run checks your code on 2 sample tests. Submit runs all 9 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.