Minimum Size Subarray Sum - Practice Coding Problems

Minimum Size Subarray Sum - 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.

A subarray is a contiguous part of an array.

Input & Output

Example 1 — Basic Case

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

› Output: 2

💡 Note: The subarray [4,3] has sum 7 which is ≥ target, and length 2 is minimal. Other valid subarrays like [2,3,1,2] have length 4.

Example 2 — Single Element

$ Input: nums = [1,4,4], target = 4

› Output: 1

💡 Note: Single element [4] already meets the target requirement with minimum length 1.

Example 3 — No Solution

$ Input: nums = [1,1,1,1,1,1,1,1], target = 11

› Output: 0

💡 Note: Total sum is 8 < 11, so no subarray can achieve target sum ≥ 11.

Constraints

1 ≤ target ≤ 10⁹
1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array of positive integers and target sum

Process

Find shortest contiguous subarray with sum ≥ target

Output

Length of minimum subarray (0 if impossible)

Key Takeaway

🎯 Key Insight: Use sliding window to efficiently find the shortest subarray by expanding when sum is too small and contracting when sum meets target

Asked in

f Facebook 45 a Amazon 38 G Google 32 M Microsoft 28

The key insight is to use a sliding window approach that expands to reach the target sum and contracts to find the minimum length. The optimal solution uses two pointers with O(n) time complexity, where each element is visited at most twice. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Subarrays	O(n³)	O(1)	Try every possible subarray and find the shortest one with sum ≥ target
Binary Search on Answer	O(n log n)	O(1)	Binary search on the answer space (1 to n) and check if target sum is achievable
Sliding Window (Two Pointers)	O(n)	O(1)	Use two pointers to maintain a window, expand when sum < target, shrink when sum ≥ target

Brute Force - Check All Subarrays — Algorithm Steps

For each starting position i
For each ending position j ≥ i
Calculate sum from i to j
If sum ≥ target, update minimum length

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subarrays

Try all starting and ending positions

Calculate Sums

Sum elements in each subarray

Find Minimum

Track shortest subarray with sum ≥ target

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* nums, int numsSize, int target) {
    int minLen = INT_MAX;
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = i; j < numsSize; j++) {
            int currentSum = 0;
            for (int k = i; k <= j; k++) {
                currentSum += nums[k];
            }
            if (currentSum >= target) {
                int len = j - i + 1;
                if (len < minLen) {
                    minLen = len;
                }
            }
        }
    }
    
    return minLen == INT_MAX ? 0 : minLen;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int nums[1000];
    int count = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[count++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int target;
    scanf("%d", &target);
    
    printf("%d\n", solution(nums, count, target));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Triple nested loops: n starting positions × n ending positions × n sum calculations

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables to track minimum length and current sum

✓ Linear Space

125.0K Views

High Frequency

~25 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Subarrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler