Problem

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

OR

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

OR

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

Variation

  1. Find the length of the smallest contiguous subarray whose sum is equal to K (Instead of greater than equal to K). Smallest subarray with Sum exactly equal to K
  2. What if the array has negative numbers as well?

Examples

Example 1:

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

Example 2:

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

Example 3:

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

Solution

Method 1 - Brute Force

The brute force approach examines all subarrays in the array, checking each one’s sum against the target value K, and return the length of subarray with the shortest length.

Code

Java
public int minSubArrayLen(int target, int[] nums) {
	int n = nums.length;
	int ans = Integer.MAX_VALUE;

	for (int i = 0; i < n; i++) {
		int currSubarraySum = 0;

		for (int j = i; j < n; j++) {
			currSubarraySum += nums[j];

			if (currSubarraySum >= target) {
				ans = Math.min(ans, j - i + 1);
				break;
			}
		}
	}

	return ans == Integer.MAX_VALUE ? 0 : ans;
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 2 - Sliding Window

In the brute force approach for finding the minimum-length subarray sum, repetitive calculations are performed across iterations.

Consider an array nums with the target sum as target:

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

Starting from the first element 3, calculate the sum of subarrays beginning at this point:

Subarray [2]           Sum = 2
Subarray [2, 3]        Sum = 5
Subarray [2, 3, 1]     Sum = 6 
Subarray [2, 3, 1, 2]  Sum = 8

Now current subarray or window’s sum is greater than or equal to K. So we update the minimum length and move on to explore subarrays starting from the next element (3).

Subarray [3]        Sum = 3
Subarray [3, 1]     Sum = 4 
Subarray [3, 1, 2]  Sum = 6
Subarray [3, 1, 2, 4]  Sum = 10

Notice that, we’re calculating the sum of the overlapping subarrays twice. For eg., we’re calculating the sum of the subarray [3, 1, 2] both in the first iteration of the outer loop as well as the second iteration.

So, we can use sliding window technique.

We can use the sliding window technique to save us from recalculating the sum of the overlapping subarrays. We will use a similar strategy explained in Maximum Sum Subarray of Size K. But there is one difference: in this problem, the sliding window size is not fixed. Instead, we need to minimize the window size.

  • Consider each subarray as a sliding window.
  • Start with a sliding window of size 1 (left=0, right=0).
  • Iterate over the array and add elements to the window until the sum becomes greater than or equal to K.
    • At this point, we have a window (subarray) that conforms to our criteria of sum >= K. Remember the length of this window as the smallest window so far.
    • Now, there is no point in adding more elements to the window because we need to find the smallest window. So we will start shrinking the window from the left until the sum becomes smaller than K. While shrinking the window, we will do two things:
      • Check if the current window length is the smallest so far. If yes, then update the minimum length.
      • Subtract the leftmost element of the window from the window sum to shrink the sliding window.

Code

Java
public class Solution {
    private int minSubArrayLen(int[] a, int K) {
        int n = a.length;

        int ans = Integer.MAX_VALUE;
        int windowSum = 0;

        int left = 0;
        for(int right = 0; right < n; right++) {
            windowSum += a[right];

            while(windowSum >= K) { /
                ans = Math.min(ans, right-left+1);
                windowSum -= a[left]; 
                left++;
            }
        }

        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

}