Leetcode-Top-150-Question-Day-5: Sliding Window

Topic : Sliding Window

Question: 1 -> 209. Minimum Size Subarray Sum

Problem Statement :

we have given an array of positive integers nums and a positive integer target, we have to return the minimal length of a subarray whose sum is greater than or equal to target.

Intuition :

If we solve it by brute force approach ,T.C will be high. We can also use Prefix-sum and binary-search approach , T.C will be n(log n), that why i choose Sliding window, so T.C will be O(n).

The sliding window technique allows us to efficiently search for the minimum length subarray that satisfies the given condition. By maintaining two pointers and adjusting the window based on the sum of elements, we can avoid unnecessary computations and achieve a time complexity of O(N), where N is the size of the input array nums.

Sliding Window Approach :

1. Initialize two pointers, left and right, to track the start and end of the current subarray, respectively. Set left and right to 0 initially.
2. Initialize a variable sum to keep track of the current sum of elements in the subarray.
3. Initialize a variable miniLen to store the minimum length found so far. Set it to the maximum possible integer value (INT_MAX).
4. Start a while loop that continues until the right pointer reaches the end of the array nums.
5. Inside the loop, add the element at index right to the sum variable.
6. Check if the sum is greater than or equal to the target value.
7. If the condition is true, enter another while loop. This loop will handle the case where the current subarray sum is equal to or greater than the target.
   i ) . Decrement the sum by subtracting the element at index left.
   ii ) . Update miniLen with the minimum length found so far (right - left + 1).
   iii ) . Increment the left pointer to move the window to the right.
   d. Repeat steps a-c until the sum is no longer greater than or equal to the target value.
8. Increment the right pointer to move the window to the right.
9. Repeat steps 5–8 until the right pointer reaches the end of the array.
10. After the loop, check if the value of miniLen is still INT_MAX, indicating that no subarray was found. In this case, return 0.
11. Otherwise, return the value of miniLen, which represents the minimum length of a subarray whose sum is greater than or equal to the target.

Complexity

• The time complexity of this solution is O(n),
• The space complexity is O(1) because we are using a constant amount of extra space for the pointers and temporary variables.

CODE:

HOPE YOU LIKE MY APPROACHE!!!

THANKYOU!!!