Minimum Size Subarray Sum Problem

Problems

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.

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.

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

What if the array has negative numbers as well?
Find the length of the smallest contiguous subarray whose sum is equal to K (Instead of greater than equal to K). #Variation 1 - Smallest subarray with sum exactly equal to K
Find Smallest Subarray with Sum Greater OR Higher than the Given Value - #Variation 2 - Smallest Subarray with sum greater than given value

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;
    }

}

Complexity

⏰ Time complexity: O(n), where n is the length of the array. This is achieved through the sliding window approach.
🧺 Space complexity: O(1)

Variation 1 - Smallest subarray with sum exactly equal to K

Here are the solutions.

Method 1 - Brute Force

This is similar to the brute force approach we discussed for the original problem. The only difference is that we’re checking if the subarray sum is equal to K instead of greater than or equal to K.

Code

Java

public class Solution {
    public int smallestSubarrayWithSum(int[] arr, int target) {
        int n = arr.length;
        int minLength = Integer.MAX_VALUE;
        int currentSum = 0;
        int start = 0;

        for (int end = 0; end < n; end++) {
            currentSum += arr[end];

            while (currentSum == target) {
                minLength = Math.min(minLength, end - start + 1);
                currentSum -= arr[start];
                start++;
            }
        }

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

Python

def smallest_subarray_with_sum(arr, target):
    n = len(arr)
    min_length = float("inf")
    current_sum = 0
    start = 0

    for end in range(n):
        current_sum += arr[end]

        while current_sum == target:
            min_length = min(min_length, end - start + 1)
            current_sum -= arr[start]
            start += 1

    return min_length if min_length != float("inf") else 0

Complexity

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

Method 2 - Sliding Window

The sliding window implementation of this variation is also similar to the implementation of the original problem. The difference is that we update the minimum length only when the windowSum is equal to K.

Code

Java

public class Solution {
    private static int minSubArrayLenWithSumK(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) { 
                windowSum -= a[left]; 
                left++; 
            }

            if(windowSum == K) {
                ans = Math.min(ans, right-left+1);
            }
        }

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

Complexity

⏰ Time complexity: O(n)
🧺 Space complexity: O(1)

Variation 2 - Smallest Subarray with sum greater than given value

Examples

Example 1:

Input: `arr = [1, 4, 45, 6, 0, 19]`, `target = 51`
Output: `3`
Explanation: The smallest subarray with sum greater than 51 is `[4, 45, 6]` which has a length of `3`.

Example 2:

Input: `arr = [1, 10, 5, 2, 7]`, `target = 9`
Output: `1`
Explanation: The smallest subarray with sum greater than 9 is `[10]` which has a length of `1`.

Method 1 - Sliding Window

Here is the approach:

Initialise minLength to the length of the array, and let x be the given integer.
Set currSum to 0 and start to 0.
Perform a linear scan of the array, adding each element to currSum.
If currSum exceeds x, subtract elements from the beginning while checking if the length of the current subarray is less than minLength. If it is, update minLength and note the indices marking the start and end of the subarray.

Code

Java

public class Solution {
    public int smallestSubarrayWithSum(int[] arr, int target) {
        int n = arr.length;
        int minLength = Integer.MAX_VALUE;
        int currentSum = 0;
        int start = 0;

        for (int end = 0; end < n; end++) {
            currentSum += arr[end];

            while (currentSum > target) {
                minLength = Math.min(minLength, end - start + 1);
                currentSum -= arr[start];
                start++;
            }
        }

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

Python

def smallest_subarray_with_sum(arr, target):
    n = len(arr)
    min_length = float("inf")
    current_sum = 0
    start = 0

    for end in range(n):
        current_sum += arr[end]

        while current_sum > target:
            min_length = min(min_length, end - start + 1)
            current_sum -= arr[start]
            start += 1

    return min_length if min_length != float("inf") else 0

Complexity

⏰ Time complexity: O(n), where n is the length of the array. This is achieved through the sliding window approach.
🧺 Space complexity: O(1)

Problems#

Variation#

Examples#

Similar Problem#

Solution#

Method 1 - Brute Force#

Code#

Java#

Complexity#

Method 2 - Sliding Window#

Code#

Java#

Complexity#

Variation 1 - Smallest subarray with sum exactly equal to K#

Method 1 - Brute Force#

Code#

Java#

Python#

Complexity#

Method 2 - Sliding Window#

Code#

Java#

Complexity#

Variation 2 - Smallest Subarray with sum greater than given value#

Examples#

Method 1 - Sliding Window#

Code#

Java#

Python#

Complexity#

Problems

Variation

Examples

Similar Problem

Solution

Method 1 - Brute Force

Code

Java

Complexity

Method 2 - Sliding Window

Code

Java

Complexity

Variation 1 - Smallest subarray with sum exactly equal to K

Method 1 - Brute Force

Code

Java

Python

Complexity

Method 2 - Sliding Window

Code

Java

Complexity

Variation 2 - Smallest Subarray with sum greater than given value

Examples

Method 1 - Sliding Window

Code

Java

Python

Complexity