Minimize a Positive-Array Target Window Length
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Return the smallest length of a nonempty contiguous subarray whose sum is at least target. If no such subarray exists, return 0. All input values and the target are positive.
```cpp
int minSubArrayLen(int target, vector<int>& nums);
```
### Examples
```text
Input: target = 10, nums = [1,2,3,7,2]
Output: 2
```
The pair 3,7 meets the target, and no single value does.
```text
Input: target = 8, nums = [1,2,3]
Output: 0
```
### Constraints
- Target is between 1 and 1000000000.
- Length is between 1 and 100000.
- Each value is between 1 and 10000.
### Optional follow-up
After finding an `O(n)` solution, provide an `O(n log n)` alternative.
Overview: Find the shortest positive-sum target window with a linear scan and a separate prefix-sum binary-search alternative.
Community answers
Answer by Coderka14
#include
using namespace std;
class Solution
{
public:
int minSubArrayLen(int target, vector& nums)
{
int n = nums.size();
int left = 0;
int sum = 0;
int ans = INT_MAX;
for (int right = 0; right < n; right++)
{
sum += nums[right];
while (sum >= target)
{
ans = min(ans, right - left + 1);
sum -= nums[left];
left++;
}
}
return ans == INT_MAX ? 0 : ans;
}
};