Leetcode 209. Minimum Size Subarray Sum

Problem Explanation

This problem is asking to return the minimal length of a contiguous subarray in which the sum of the elements is greater than or equal to the given sum.

To make this concept clearer, let's consider an example:

Input: s = 7, nums = [2,3,1,2,4,3] Output: 2 Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Approach to the solution

The solution uses a sliding window technique and two-pointer methodology. We initialize two pointers l and r at index 0. r is used to extend the current subarray, and l is used to contract it. For each variant of l and r, we try to update our answer ans.

Visual:

1
2
3s = 7, nums = [2,3,1,2,4,3]
4Initially: l=0, r=0, sum=0, ans = INT_MAX
5
6Add nums[r] until sum >= s
7--> l=0, r=0, sum=2
8--> l=0, r=1, sum=5
9--> l=0, r=2, sum=6
10--> l=0, r=3, sum=8
11
12Now, sum >= s. Update ans with min(ans, r-l+1) = min(INT_MAX, 4) = 4
13Then, subtract nums[l] from the sum and increment l
14--> l=1, r=3, sum=6
15Sum is less than s. Increment r and add nums[r] to sum
16--> l=1, r=4, sum=10
17Now, sum >= s. Update ans with min(ans, r-l+1) = min(4, 4) = 4
18Subtract nums[l] from sum and increment l
19--> l=2, r=4, sum=7
20Now, sum >= s. Update ans with min(ans, r-l+1) = min(4, 3) = 3
21Subtract nums[l] from sum and increment l
22--> l=3, r=4, sum=6
23Sum is less than s. Increment r and add nums[r] to sum
24--> l=3, r=5, sum=9
25Now, sum >= s. Update ans with min(ans, r-l+1) = min(3, 3) = 3
26Subtract nums[l] from sum and increment l
27--> l=4, r=5, sum=5
28Increment r and add nums[r] to sum
29--> l=4, r=6 (out of range), sum=5
30If r has reached the end of array and we can't form a subarray with sum>=s, then break.
31If ans = INT_MAX, change it to 0.
32Return ans.

Python solution

1
2python
3class Solution:
4    def minSubArrayLen(self, s: int, nums) -> int:
5        ans = float("inf")
6        sum = 0
7        l = 0
8
9        for r in range(len(nums)):
10            sum += nums[r]
11            while sum >= s:
12                ans = min(ans, r - l + 1)
13                sum -= nums[l]
14                l += 1
15
16        return ans if ans != float("inf") else 0

Java solution

1
2java
3class Solution {
4    public int minSubArrayLen(int s, int[] nums) {
5        int ans = Integer.MAX_VALUE;
6        int sum = 0;
7        int l = 0;
8
9        for (int r=0; r < nums.length; r++) {
10            sum += nums[r];
11            while (sum >= s) {
12                ans = Math.min(ans, r - l + 1);
13                sum -= nums[l];
14                l++;
15            }
16        }
17        return (ans != Integer.MAX_VALUE) ? ans : 0;
18    }
19}

Javascript solution

1
2javascript
3var minSubArrayLen = function(s, nums) {
4    let ans = Infinity;
5    let sum = 0;
6    let l = 0;
7
8    for (let r = 0; r < nums.length; r++) {
9        sum += nums[r];
10        while (sum >= s) {
11            ans = Math.min(ans, r - l + 1);
12            sum -= nums[l];
13            l++;
14        }
15    }
16    return (ans != Infinity) ? ans : 0;
17};

C++ solution

1
2c++
3class Solution {
4public:
5    int minSubArrayLen(int s, vector<int>& nums) {
6        int ans = INT_MAX;
7        int sum = 0;
8        int l = 0;
9
10        for (int r = 0; r < nums.size(); r++) {
11            sum += nums[r];
12            while (sum >= s) {
13                ans = min(ans, r - l + 1);
14                sum -= nums[l];
15                l++;
16            }
17        }
18        return (ans != INT_MAX) ? ans : 0;
19    }
20};

C# solution

1
2csharp
3public class Solution {
4    public int MinSubArrayLen(int s, int[] nums) {
5        int ans = int.MaxValue;
6        int sum = 0;
7        int l = 0;
8
9        for (int r = 0; r < nums.Length; r++) {
10            sum += nums[r];
11            while (sum >= s) {
12                ans = Math.Min(ans, r - l + 1);
13                sum -= nums[l];
14                l++;
15            }
16        }
17        return (ans != int.MaxValue) ? ans : 0;
18    }
19}

The technique used here is two pointer methodology which is used to perform the sliding window approach. It usually helps to find subarray in an array which satisfies some condition. In this case, we're looking for the smallest subarray length which when summed up is greater or equal to 's'.

These solutions are straightforward, having time and space complexities of O(n) and O(1), respectively. In each, we create a 'window' of array elements by moving right pointer to the next position until we reach a sum that's greater than or equal to 's'. At that point, we move the left pointer to the right and subtract its value from the sum. We continue this process (increasing the right pointer and shrinking the window from the left if needed) until we've traversed the whole array.

The values of 'l', 'r' and 'sum' are updated at each stage; once 'r' reaches the end of the array, and if 'sum' is less than 's', the process breaks and the function returns the length of the smallest subarray. If no such subarray is found (i.e., if 'sum' is never greater or equal to 's'), the function returns 0.

This approach ensures that every element is visited just once, hence, it has a time complexity of O(n). The space complexity is O(1) since extra space does not increase with the increase in input size. Thus, this solves the problem in a very efficient manner.