LeetCode - Minimum Size Subarray Sum

Hello Code Recipian! Welcome back to another article on leetcode problem solutions. Today we will be solving leetcode problem no. 209, Minimum Size Subarray Sum. This problem also features in GeeksForGeeks, Smallest subarray with sum greater than a given value.

Problem Statement: Minimum Size Subarray Sum

Given an array of positive integers nums and a positive number target, find the length of the smallest contiguous subarray whose sum is greater than or equal to target. If no such subarray exists, return 0.

Example 1:

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: [4,3] is the minimal length subarray with sum = 7.

Example 2:

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

Example 3:

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

Constraints:

• 1 <= target <= 10^9

• 1 <= nums.length <= 10^5

• 1 <= nums[i] <= 10^4

Solution

To solve this problem we will be using the sliding window technique that we discussed in our previous article. The difference here is that, in the previous solution we made use of a fixed sliding window, but here we will be using a window that expands or contracts as needed.

If windowSum is less than target we expand the window (towards right) and we shrink the window (from left) if windowSum is greater than or equal to target. The logic behind this expanding and shrinking is, as per problem statement, we need a subarray sum greater than or equal to target, and when:

• windowSum >= target, if we expand the window, we we will only get a bigger sum (since nums is a positive numbers array). This is the reason we shrink the window.

• windowSum < target, if we shrink the window, we will obviously get a smaller sum. Hence, we expand the window.

If this point is clear, let's now see how we can solve the problem using this logic.

Algorithm

Below is a step by step explanation of how this algorithm works:

1. Initialize variables:

   Initialize 4 variables: minLength, windowSum, windowStart, windowEnd.

   1. minLength is used to store our result (minimum length of subarray greater than or equal to target). This is initially set to maximum value for comparison purpose (since we want to calculate minimum length).

   2. windowSum is used to store the sum of the current window. This is initially set to 0.

   3. windowStart is used to store the starting index of our window  in nums. This is initially set to 0.

   4. windowEnd is used to store the ending index of our window in nums. This is initially set to 0.

2. Define outer loop:

   Using windowEnd we loop through the nums array starting from the 0th index till the last the last index. In each iteration of the outer loop, we perform the following operations:

   1. Add the number represented by the current windowEnd index to windowSum. This step is used to expand the window (towards the right) for the case where, windowSum >= target.

   2. Define an inner loop that executes only if our current windowSum is greater than or equal to target. This loop is used to shrink our window as long as windowSum >= target. The inner loop does the following things:

      1. Since windowSum >= target, we update our result minLength, if necessary.

      2. Since we need to shrink the window (from left), we subtract the first element in the original window from windowSum.

      3. Also, since we are discarding the first element, we increment windowStart variable.

3. Return result:

   Finally, before returning the we need to handle the case when no subarray with sum greater than or equal to target exists. For such cases, our result variable minLength, will never be updated (since the execution does not enter the inner loop). Hence it's value will still be maxInt value that we had set initially. Therefore, we return 0, as mentioned in the problem statement.

   
   

   For all other cases, we return the value in minLength as is.

Simulation

Below diagram shows a pictorial depiction of the working of this algorithm:

Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses:

1. Udemy Video Tutorials - Available at 95% off

2. System Design Interview Complete Guide

3. Cracking The Coding Interview - Most Preferred Book For Coding Interviews

4. Data Structures And Algorithms - A Complete Guide 

5. Learn In-Demand Tech Skills And Stay Ahead Of Others

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

C++ Solution

C# Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

Complexity Analysis

Time Complexity

Even though we have nested loops, if you observe carefully, we process each elements in nums array at most twice, once for adding in the outer loop and once for removing in the inner loop. Hence, the overall time complexity of this algorithm is O(n) + O(n) = O(n).

Space Complexity

The space complexity of this solution is O(1), since we are not using any extra space apart from variables like minLength, windowSum, windowStart, windowEnd which require constant auxiliary space, O(1).

That brings us to the end of this article. We sincerely appreciate the time you have taken to read through it. If there are any questions, feel free to ask them in the comments below. We're here to help and will gladly answer your queries.

If you enjoyed this article, please subscribe to our website and Youtube channel. Your support inspires us to create more such articles in the future.

Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section. There's a wealth of knowledge waiting for you there!

Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.

Follow us: YouTube, Facebook, Twitter, LinkedIn, Tumblr, Instagram.