minSizeSubarraySum.md

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

Examples:

Example 1:

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

Example 2:

Input: target = 15, nums = [2, 2, 2, 2, 2] Output: 0

---

Algorithmic Steps

This problem is efficiently solved using the sliding window technique without requiring any special data structures. The approach can be summarized as follows:

1. Initialize two pointers, left and right, both at 0. These represent the current window boundaries.
2. Initialize a variable total to 0 to keep track of the sum of the current window.
3. Initialize minLength to a very large number (e.g., infinity) to represent the length of the smallest valid subarray found so far.
4. Iterate through the array with the right pointer:
   • Add nums[right] to total.
   • While total is greater than or equal to target:
     • Update minLength to the smaller value between the current minLength and the window size (right - left + 1).
     • Subtract nums[left] from total and move the left pointer forward to try and find a smaller valid window.
5. Continue until the right pointer reaches the end of the array.
6. If minLength is still infinity (meaning no valid subarray was found), return 0. Otherwise, return minLength.

---

Time and Space Complexity

• Time Complexity: O(n)
  The array is traversed at most twice (once by each pointer), resulting in linear time complexity.

• Space Complexity: O(1)
  No additional data structures are used; only a fixed number of variables are maintained.