https://leetcode.com/problems/minimum-size-subarray-sum/description/?envType=study-plan-v2&envId=top-interview-150

C++

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0;
        int curr_sum = 0;
        int max_length = INT_MAX;

        for(int right = 0; right < nums.size(); right++){
            curr_sum += nums[right];

            while (curr_sum >= target){
                max_length = min(max_length, right - left + 1);
                curr_sum -= nums[left];
                left++;
            }
        }

        return max_length == INT_MAX ? 0 : max_length;
    }
};

Complexity

Here $n$ is the length of nums.

• Time complexity: $O(n)$.
  • You may be thinking: there is an inner while loop inside another for loop, isn't the time complexity $O(n^2)$? The reason it is still $O(n)$ is because the right pointer right can move $n$ times and the left pointer left can move also $n$ times in total. The inner loop is not running $n$ times for each iteration of the outer loop. A sliding window guarantees a maximum of $2n$ window iterations. This is what is referred to as amortized analysis - even though the worst case for an iteration inside the for loop is $O(n)$, it averages out to $O(1)$ when you consider the entire runtime of the algorithm.
• Space complexity: $O(1)$.
  • We are not using any extra space other than a few integer variables:left, right, sumOfCurrentWindow, and res, which takes up constant space each.