Find shortest subarray meeting target sum
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an integer array nums (values may be negative) and an integer T, return the length of the shortest non-empty contiguous subarray whose sum is at least T; return -1 if no such subarray exists. Optimize for n up to 200,000. Explain your approach, prove its correctness, analyze time and space complexity, and implement an O(n) solution.
Quick Answer: Find shortest subarray meeting target sum evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Given an integer array `nums` (values may be negative) and an integer `T`, return the length of the shortest non-empty contiguous subarray whose sum is at least `T`. Return `-1` if no such subarray exists.
The array can be large (n up to 200,000), so you must implement an O(n) solution rather than checking every subarray.
**Example 1:**
```
Input: nums = [1], T = 1
Output: 1
```
**Example 2:**
```
Input: nums = [1, 2], T = 4
Output: -1
```
**Example 3:**
```
Input: nums = [2, -1, 2], T = 3
Output: 3
```
**Approach.** Because the values can be negative, the classic sliding-window-over-the-array technique does not apply (extending a window can decrease the running sum). Build the prefix-sum array `P` where `P[i]` is the sum of the first `i` elements. A subarray `nums[j..i-1]` has sum `P[i] - P[j]`, and we want the smallest `i - j` with `P[i] - P[j] >= T`.
Scan `i` from `0` to `n` while keeping a deque of candidate start indices `j` whose prefix sums are strictly increasing. For each `i`: (1) while the front `j` satisfies `P[i] - P[j] >= T`, record `i - j` and pop the front (it can never give a shorter valid window for a later `i`); (2) while the back's prefix sum is `>= P[i]`, pop it (a smaller or equal prefix sum at a larger index dominates it as a future start); (3) push `i`. The deque stays monotonically increasing in prefix sum, each index is pushed and popped at most once, giving O(n).
Constraints
- 1 <= n <= 200000 (n may also be 0 for an empty array, in which case return -1)
- -10^4 <= nums[i] <= 10^4
- Subarray sums can exceed 32-bit range; use a 64-bit accumulator (long / long long) in typed languages
- T may be any integer (positive, negative, or zero)
- The subarray must be non-empty and contiguous
Examples
Input: ([1], 1)
Expected Output: 1
Explanation: The single element 1 already meets T=1, length 1.
Input: ([1, 2], 4)
Expected Output: -1
Explanation: Max subarray sum is 1+2=3 < 4, so no valid subarray.
Hints
- Brute force over all O(n^2) subarrays is too slow for n = 200,000. Reframe the problem using prefix sums: subarray nums[j..i-1] has sum P[i] - P[j].
- Because values can be negative, a plain sliding window fails. Maintain a deque of candidate start indices whose prefix sums are kept strictly increasing.
- For each i: pop from the FRONT while P[i] - P[front] >= T (record the window length — a valid front can't help a later, longer window), then pop from the BACK any index whose prefix sum is >= P[i] (it's dominated).