Scale Engineer

Minimum Size Subarray Sum

Med
#0197Time: O(n²) where n is the length of the array as we need to check all possible subarraysSpace: O(1) as we only use a constant amount of extra space8 companies
Patterns
Sliding WindowPrefix Sum
Algorithms
Binary Search
Data structures
Array
Companies
DoorDashGoldman SachsNvidiaOracle

Prompt

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 <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104

 

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

3 approaches with complexity analysis and trade-offs.

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

Algorithm

  1. Initialize minLength as Integer.MAX_VALUE
  2. 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
  3. Return 0 if minLength is still Integer.MAX_VALUE, else return minLength

Walkthrough

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

Time

O(n²) where n is the length of the array as we need to check all possible subarrays

Space

O(1) as we only use a constant amount of extra space

Trade-offs

Pros

  • Simple to understand and implement

  • Works for all test cases

Cons

  • Very inefficient for large arrays

  • Time complexity is quadratic

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem