Minimum Size Subarray Sum

MEDIUM

Description

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.

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 = 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⁹
1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁴

Follow up: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log(n)).

Approaches

Checkout 3 different approaches to solve Minimum Size Subarray Sum. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

Check all possible subarrays and find the minimum length subarray with sum greater than or equal to target.

Algorithm

Initialize minLength as Integer.MAX_VALUE
For each index i from 0 to n-1:
- Initialize sum as 0
- For each index j from i to n-1:
  - Add nums[j] to sum
  - If sum >= target:
    - Update minLength if current length (j-i+1) is smaller
    - Break inner loop
Return 0 if minLength is still Integer.MAX_VALUE, else return minLength

For each index i, we try all possible subarrays starting from i and calculate their sum. If we find a sum that is greater than or equal to target, we update the minimum length if the current subarray length is smaller.

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int minLength = Integer.MAX_VALUE;
        
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum >= target) {
                    minLength = Math.min(minLength, j - i + 1);
                    break;
                }
            }
        }
        
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }
}

Complexity Analysis

Time Complexity: O(n²) where n is the length of the array as we need to check all possible subarraysSpace Complexity: O(1) as we only use a constant amount of extra space

Pros and Cons

Pros:

Simple to understand and implement
Works for all test cases

Cons:

Very inefficient for large arrays
Time complexity is quadratic

Code Solutions

Checking out 4 solutions in different languages for Minimum Size Subarray Sum. Click on different languages to view the code.

public class Solution {
    public int MinSubArrayLen(int target, int[] nums) {
        int n = nums.Length;
        long s = 0;
        int ans = n + 1;
        for (int i = 0, j = 0; i < n; ++i) {
            s += nums[i];
            while (s >= target) {
                ans = Math.Min(ans, i - j + 1);
                s -= nums[j++];
            }
        }
        return ans == n + 1 ? 0 : ans;
    }
}

Video Solution

Watch the video walkthrough for Minimum Size Subarray Sum

Algorithms:

Binary Search

Patterns:

Sliding WindowPrefix Sum

Data Structures:

Array

Companies:

DoorDash |Goldman Sachs |Nvidia |Oracle |