# 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](https://leetcode.com/problems/minimum-size-subarray-sum)

**Example 1:**

```plaintext
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:**

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

**Example 3:**

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

**Constraints:**

```plaintext
- 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:

```cpp
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.

```plaintext
- 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**

```cpp
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**

```go
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**

```javascript
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;
};
```

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

```plaintext
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.
```