Problem Statement

Given an array of positive integers nums and an integer S, find the minimal length of a contiguous subarray of which the sum is greater than or equal to S. If no such subarray exists, return 0 instead.

Examples

Example 1:

Input: nums = [2, 3, 1, 2, 4, 3], S = 7
Output: 2

Explanation: The subarray [4, 3] has the minimal length under the problem constraint.

Example 2:

Input: nums = [1, 4, 4], S = 4
Output: 1

Explanation: The single element subarray [4] satisfies the condition.

Example 3:

Input: nums = [1, 1, 1, 1, 1, 1, 1, 1], S = 11
Output: 0

Explanation: There is no subarrary that has a sum >= 11.

Different Approaches

1️⃣ Brute Force Approach

Approach:

Iterate over all possible subarrays, calculate their sums, and check if the sum is greater than or equal to the target.

Code:

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int minSubarrayLenBruteForce(int S, vector<int>& nums) {
    int n = nums.size();
    int minLen = INT_MAX;

    for (int i = 0; i < n; ++i) {
        int currentSum = 0;
        for (int j = i; j < n; ++j) {
            currentSum += nums[j];
            if (currentSum >= S) {
                minLen = min(minLen, j - i + 1);
                break; // No need to check longer subarrays
            }
        }
    }

    return minLen == INT_MAX ? 0 : minLen;
}

Complexity Analysis:

• Time Complexity: O(n^2)
  • As two nested loops for subarrays.
• Space Complexity: O(1)
  • No extra space is used.

2️⃣