# LeetCode - Minimum Size Subarray Sum

## Problem statement

Given an array of positive integers `nums` and a positive integer `target`, return the minimal length of a subarray whose sum is greater than or equal to target. If there is no such subarray, return `0` instead.

Problem statement taken from: https://leetcode.com/problems/minimum-size-subarray-sum

Example 1:

``````Input: target = 7, nums = [2, 3, 1, 2, 4, 3]
Output: 2
Explanation: The subarray [4, 3] has the minimal length under the problem constraint.
``````

Example 2:

``````Input: target = 4, nums = [1, 4, 4]
Output: 1
``````

Example 3:

``````Input: target = 11, nums = [1, 1, 1, 1, 1, 1, 1, 1]
Output: 0
``````

Constraints:

``````- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums.length <= 10^4
``````

### Explanation

#### Brute force approach

A naive approach is to run two nested loops. The outer loop selects a starting element, and the inner loop iterates over the array. Whenever the sum of elements between the start and end becomes more than target, we update the minimum length if current length is smaller than the smallest length so far.

A C++ snippet of this approach is as below:

``````int minLength = n + 1;

for (int start = 0; start < n; start++) {
int currentSum = nums[start];

if (currentSum > x) return 1;

for (int end = start + 1; end < n; end++) {
currentSum += nums[end];

if (currentSum > x && (end - start + 1) < minLength)
minLength = (end - start + 1);
}
}

return minLength;``````

The time-complexity of the above approach is O(n^2), and the space complexity is O(1).

#### Efficient solution

An efficient approach is to use a sliding window approach. Let's jump to the algorithm to understand it clearly.

``````- set l = 0, r = -1
sum = 0
minLength = nums.size() + 1

- loop while l < nums.size()
- if r + 1 < nums.size() && sum < target
- sum += nums[++r]
- else
- sum -= nums[l++]

- if sum >= target
- minLength = min(minLength, r - l + 1)
- loop end

- return minLength == nums.size() + 1 ? 0 : minLength
``````

The time complexity of the above approach is O(n), and the space complexity is O(1).

Let's check our algorithm in C++, Golang, and Javascript.

#### C++ solution

``````class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int l = 0, r = -1;
int sum = 0;
int minLength = nums.size() + 1;

while(l < nums.size()) {
if(r + 1 < nums.size() && sum < target) {
sum += nums[++r];
} else {
sum -= nums[l++];
}

if(sum >= target) {
minLength = min(minLength, r - l + 1);
}
}

return minLength == nums.size() + 1 ? 0 : minLength;
}
};``````

#### Golang solution

``````func minSubArrayLen(target int, nums []int) int {
l, r := 0, -1
sum := 0
minLength := len(nums) + 1

for ;l < len(nums); {
if r + 1 < len(nums) && sum < target {
r += 1
sum += nums[r]
} else {
sum -= nums[l]
l += 1
}

if sum >= target {
minLength = min(minLength, r - l + 1)
}
}

if minLength == len(nums) + 1 {
return 0
}

return minLength
}

func min(a, b int) int {
if a < b {
return a
}

return b
}``````

#### Javascript solution

``````var minSubArrayLen = function(target, nums) {
let l = 0, r = -1;
let sum = 0;
let minLength = nums.length + 1;

while(l < nums.length) {
if(r + 1 < nums.length && sum < target) {
sum += nums[++r];
} else {
sum -= nums[l++];
}

if(sum >= target) {
minLength = Math.min(minLength, r - l + 1);
}
}

return minLength == nums.length + 1 ? 0 : minLength;
};``````

#### Dry Run

Let's dry-run our algorithm to see how the solution works.

``````Input: target = 7, nums = [2, 3, 1, 2, 4, 3]

Step 1: l = 0, r = -1
sum = 0
minLength = nums.size() + 1
= 6 + 1
= 7

Step 2: loop while l < nums.size()
0 < 6
true

if r + 1 < nums.size() && sum < target
-1 + 1 < 6 && 0 < 7
0 < 6 && 0 < 7
true

sum = sum + nums[++r]
= 0 + nums[0]
= 0 + 2
= 2

r = 0

if sum >= target
2 >= 7
false

Step 3: loop while l < nums.size()
0 < 6
true

if r + 1 < nums.size() && sum < target
0 + 1 < 6 && 2 < 7
1 < 6 && 2 < 7
true

sum = sum + nums[++r]
= 2 + nums[1]
= 2 + 3
= 5

r = 1

if sum >= target
5 >= 7
false

Step 4: loop while l < nums.size()
0 < 6
true

if r + 1 < nums.size() && sum < target
1 + 1 < 6 && 5 < 7
2 < 6 && 5 < 7
true

sum = sum + nums[++r]
= 5 + nums[2]
= 5 + 1
= 6

r = 2

if sum >= target
6 >= 7
false

Step 5: loop while l < nums.size()
0 < 6
true

if r + 1 < nums.size() && sum < target
2 + 1 < 6 && 6 < 7
3 < 6 && 6 < 7
true

sum = sum + nums[++r]
= 6 + nums[3]
= 6 + 2
= 8

r = 3

if sum >= target
8 >= 7
true

minLength = min(minLength, r - l + 1)
= min(7, 3 - 0 + 1)
= min(7, 4)
= 4

Step 6: loop while l < nums.size()
0 < 6
true

if r + 1 < nums.size() && sum < target
3 + 1 < 6 && 8 < 7
4 < 6 && 8 < 7
false
else
sum = sum - nums[l++]
= 8 - nums[0]
= 8 - 2
= 6

l = 1

Step 7: loop while l < nums.size()
1 < 6
true

if r + 1 < nums.size() && sum < target
3 + 1 < 6 && 6 < 7
4 < 6 && 6 < 7
true

sum = sum + nums[++r]
= 6 + nums[4]
= 6 + 4
= 10

r = 4

if sum >= target
10 >= 7
true

minLength = min(minLength, r - l + 1)
= min(4, 4 - 1 + 1)
= min(4, 4)
= 4

Step 8: loop while l < nums.size()
1 < 6
true

if r + 1 < nums.size() && sum < target
4 + 1 < 6 && 10 < 7
5 < 6 && 10 < 7
false
else
sum = sum - nums[l++]
= 10 - nums[1]
= 10 - 3
= 7

l = 2

if sum >= target
7 >= 7
true

minLength = min(minLength, r - l + 1)
= min(4, 4 - 2 + 1)
= min(4, 3)
= 3

Step 9: loop while l < nums.size()
2 < 6
true

if r + 1 < nums.size() && sum < target
4 + 1 < 6 && 7 < 7
5 < 6 && 7 < 7
false
else
sum = sum - nums[l++]
= 7 - nums[2]
= 7 - 1
= 6

l = 3

if sum >= target
6 >= 7
false

Step 10: loop while l < nums.size()
3 < 6
true

if r + 1 < nums.size() && sum < target
4 + 1 < 6 && 6 < 7
5 < 6 && 6 < 7
true

sum = sum + nums[++r]
= 6 + nums[5]
= 6 + 3
= 9

r = 5

if sum >= target
9 >= 7
true

minLength = min(minLength, r - l + 1)
= min(3, 5 - 3 + 1)
= min(3, 3)
= 3

Step 11: loop while l < nums.size()
3 < 6
true

if r + 1 < nums.size() && sum < target
5 + 1 < 6 && 9 < 7
6 < 6 && 9 < 7
false
else
sum = sum - nums[l++]
= 9 - nums[3]
= 9 - 2
= 7

l = 4

if sum >= target
7 >= 7
true

minLength = min(minLength, r - l + 1)
= min(3, 5 - 4 + 1)
= min(3, 2)
= 2

Step 12: loop while l < nums.size()
4 < 6
true

if r + 1 < nums.size() && sum < target
5 + 1 < 6 && 7 < 7
6 < 6 && 7 < 7
false
else
sum = sum - nums[l++]
= 7 - nums[4]
= 7 - 4
= 3

l = 5

if sum >= target
3 >= 7
false

Step 13: loop while l < nums.size()
5 < 6
true

if r + 1 < nums.size() && sum < target
5 + 1 < 6 && 3 < 7
6 < 6 && 3 < 7
false
else
sum = sum - nums[l++]
= 3 - nums[5]
= 3 - 3
= 0

l = 6

if sum >= target
0 >= 7
false

Step 14: loop while l < nums.size()
6 < 6
false

Step 15: minLength == nums.size() + 1 ? 0 : minLength
2 == 6 + 1 ? 0 : 2
2 == 7 ? 0 : 2
false

We return the result as 2.
``````