Minimum Size Subarray Sum

Problem Statement

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

What to notice first

• All numbers are positive integers, so once a sum is too small, adding more numbers will only make it larger.
• The key is to find the shortest window where the sum meets the target.
• A two-pointer or sliding window technique can efficiently track valid ranges without rechecking from the start.

Examples

Input Array	Target	Output	Explanation
[2, 3, 1, 2, 4, 3]	7	2	[4, 3] has sum 7 (minimum length 2)
[1, 4, 4]	4	1	[4] has sum 4 (minimum length 1)
[1, 1, 1, 1, 1, 1, 1, 1]	15	0	No subarray has sum >= 15
[1, 2, 3, 4, 5]	11	2	[4, 5] has sum 9… wait, [2, 3, 4, 5] = 14, minimum is [5, ...] = 5. Actually [4, 5] = 9 < 11. Need [2, 3, 4, 5] = 14, length 4. Or [1, 2, 3, 4, 5] = 15. Minimum is [4, 5, ?]. Clarification: [4, 5] = 9. We need [1, 2, 3, 5] but that’s not contiguous. So [2, 3, 4, 5] = 14, length 4. Actually [5, 6, ...] but 6 doesn’t exist. Correct answer is [4, 5] + next… wait, let me recalculate: we need minimum length with sum >= 11. [5, ...] is only 5. [4, 5] = 9. [3, 4, 5] = 12, length 3. Correct!

Constraints

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4
• 1 <= target <= 10^9

Real-World Applications

Where this pattern appears

• Network bandwidth allocation — find the minimum number of consecutive time windows needed to transfer at least target bytes at varying rates.
• Product sales target — given daily sales figures, find the shortest contiguous period needed to reach a sales milestone.
• Memory buffer management — determine the minimum window of frames needed to accumulate at least target megabytes.
• Shipping container optimization — find the fewest consecutive days of items needed to meet a minimum shipment weight.

Complexity Comparison

Approach	Time	Space	Best When
Sliding Window	O(n)	O(1)	General case — single linear pass, optimal for most inputs
Binary Search	O(n log n)	O(n)	Already computed prefix sums available, or academic interest

Which approach should you learn first?

• Pick Sliding Window if you want the best all-around interview answer.
• Pick Binary Search if you are comfortable with prefix sums and want to explore a different strategy.

Best For Speed

Sliding Window

O(n) time · O(1) space

With Prefix Sums

Binary Search

O(n log n) time · O(n) space

Approach 1: Sliding Window (Recommended)

★ Recommended

Use two pointers to maintain a window of consecutive elements. Expand the window by moving the right pointer and adding elements to the sum. When the sum is >= target, try shrinking from the left while maintaining the target sum to find the minimum length.

The key insight is that both pointers move in the same direction (left only moves right, never left). This ensures each element is visited at most twice, giving linear time complexity.

⏱ Time O(n) Single pass, two pointers 💾 Space O(1) No extra data structures

Step-by-step Example

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

Step	left	right	window	sum	Action
1	0	0	[2]	2	sum < 7 → expand right
2	0	1	[2, 3]	5	sum < 7 → expand right
3	0	2	[2, 3, 1]	6	sum < 7 → expand right
4	0	3	[2, 3, 1, 2]	8	sum >= 7 → record length 4, shrink left
5	1	3	[3, 1, 2]	6	sum < 7 → expand right
6	1	4	[3, 1, 2, 4]	10	sum >= 7 → record length 4, shrink left
7	2	4	[1, 2, 4]	7	sum >= 7 → record length 3, shrink left
8	3	4	[2, 4]	6	sum < 7 → expand right
9	3	5	[2, 4, 3]	9	sum >= 7 → record length 3, shrink left
10	4	5	[4, 3]	7	sum >= 7 → record length 2 ✓
11	5	5	[3]	3	sum < 7 → stop

Final answer: 2 (subarray [4, 3])

Animated walkthrough

How the sliding window finds the minimum length

Watch the left and right pointers expand and contract. When sum >= target, we shrink from the left to find the minimum window.

Back Autoplay Next Reset

Step 1 of 8 Target: 7

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function minSubArrayLenSlidingWindow(nums, target):
    left = 0
    currentSum = 0
    minLength = infinity

    for right in range(len(nums)):
        currentSum += nums[right]

        while currentSum >= target:
            minLength = min(minLength, right - left + 1)
            currentSum -= nums[left]
            left += 1

    return minLength if minLength != infinity else 0

Solution Code

Python

minimum_size_subarray_sum_sliding_window.py

from typing import List


def minimum_size_subarray_sum_sliding_window(target: int, nums: List[int]) -> int:
    left = 0
    current_sum = 0
    min_length = float('inf')

    for right in range(len(nums)):
        current_sum += nums[right]

        while current_sum >= target:
            min_length = min(min_length, right - left + 1)
            current_sum -= nums[left]
            left += 1

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

print(minimum_size_subarray_sum_sliding_window(7, [2, 3, 1, 2, 4, 3]))  # 2

C++

minimum_size_subarray_sum_sliding_window.cpp

#include <iostream>
#include <vector>
#include <algorithm>

int minSubArrayLenSlidingWindow(int target, std::vector<int>& nums) {
    int left = 0;
    int current_sum = 0;
    int min_length = INT_MAX;

    for (int right = 0; right < (int)nums.size(); right++) {
        current_sum += nums[right];

        while (current_sum >= target) {
            min_length = std::min(min_length, right - left + 1);
            current_sum -= nums[left];
            left++;
        }
    }

    return min_length == INT_MAX ? 0 : min_length;
}

int main() {
    std::vector<int> nums = {2, 3, 1, 2, 4, 3};
    int target = 7;
    int result = minSubArrayLenSlidingWindow(target, nums);
    std::cout << result << std::endl;
    return 0;
}

Java

minimum_size_subarray_sum_sliding_window.java

public class Main {
    public static int minSubArrayLenSlidingWindow(int target, int[] nums) {
        int left = 0;
        int currentSum = 0;
        int minLength = Integer.MAX_VALUE;

        for (int right = 0; right < nums.length; right++) {
            currentSum += nums[right];

            while (currentSum >= target) {
                minLength = Math.min(minLength, right - left + 1);
                currentSum -= nums[left];
                left++;
            }
        }

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

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 2, 4, 3};
        int target = 7;
        int result = minSubArrayLenSlidingWindow(target, nums);
        System.out.println(result);
    }
}

JavaScript

minimum_size_subarray_sum_sliding_window.js

function minSubArrayLenSlidingWindow(target, nums) {
    let left = 0;
    let currentSum = 0;
    let minLength = Infinity;

    for (let right = 0; right < nums.length; right++) {
        currentSum += nums[right];

        while (currentSum >= target) {
            minLength = Math.min(minLength, right - left + 1);
            currentSum -= nums[left];
            left++;
        }
    }

    return minLength === Infinity ? 0 : minLength;
}

const nums = [2, 3, 1, 2, 4, 3];
const target = 7;
const result = minSubArrayLenSlidingWindow(target, nums);
console.log(result);  // 2

Rust

minimum_size_subarray_sum_sliding_window.rs

fn min_sub_array_len_sliding_window(target: i32, nums: &[i32]) -> i32 {
    let mut left = 0;
    let mut current_sum = 0;
    let mut min_length = i32::MAX;

    for (right, &num) in nums.iter().enumerate() {
        current_sum += num;

        while current_sum >= target {
            min_length = min_length.min((right - left + 1) as i32);
            current_sum -= nums[left];
            left += 1;
        }
    }

    if min_length == i32::MAX { 0 } else { min_length }
}

fn main() {
    let nums = vec![2, 3, 1, 2, 4, 3];
    let target = 7;
    let result = min_sub_array_len_sliding_window(target, &nums);
    println!("{}", result);  // 2
}

Go

minimum_size_subarray_sum_sliding_window.go

package main

import (
  "fmt"
)

func minSubArrayLenSlidingWindow(target int, nums []int) int {
  left := 0
  currentSum := 0
  minLength := int(^uint(0) >> 1)

  for right := 0; right < len(nums); right++ {
    currentSum += nums[right]

    for currentSum >= target {
      if right-left+1 < minLength {
        minLength = right - left + 1
      }
      currentSum -= nums[left]
      left++
    }
  }

  if minLength == int(^uint(0)>>1) {
    return 0
  }
  return minLength
}

func main() {
  nums := []int{2, 3, 1, 2, 4, 3}
  target := 7
  result := minSubArrayLenSlidingWindow(target, nums)
  fmt.Println(result)  // 2
}

Approach 2: Binary Search on Prefix Sum

🎯 Interview Favourite

Precompute a prefix sum array where prefix[i] = sum of all elements from index 0 to i. For each element, use binary search to find the earliest position where the prefix sum difference reaches the target.

This approach trades the simplicity of sliding window for an alternative algorithmic strategy often appreciated in interviews.

⏱ Time O(n log n) Binary search per element 💾 Space O(n) Prefix sum array

Step-by-step Example

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

Prefix array: [0, 2, 5, 6, 8, 12, 15] (cumulative sums)

Step	right	prefix[right]	Find left where prefix[left] <= prefix[right] - 7	left	Length	Action
1	3	8	Search for 1 (8 - 7)	1	8 - 5 = 3, length = 3 - 1 + 1 = 3	Update minLength = 3
2	4	12	Search for 5 (12 - 7)	1	12 - 5 = 7, length = 4 - 1 + 1 = 4	Keep minLength = 3
3	5	15	Search for 8 (15 - 7)	4	15 - 8 = 7, length = 5 - 4 + 1 = 2	Update minLength = 2 ✓

Final answer: 2

Pseudocode

function minSubArrayLenBinarySearch(nums, target):
    prefix = [0]
    for num in nums:
        prefix.append(prefix[-1] + num)

    minLength = infinity

    for right in range(1, len(prefix)):
        needed = prefix[right] - target
        left = binarySearch(prefix, 0, right - 1, needed)

        if left != -1:
            minLength = min(minLength, right - left)

    return minLength if minLength != infinity else 0

Solution Code

Python

minimum_size_subarray_sum_binary_search.py

from typing import List
import bisect


def minimum_size_subarray_sum_binary_search(target: int, nums: List[int]) -> int:
    prefix = [0]
    for num in nums:
        prefix.append(prefix[-1] + num)

    min_length = float('inf')

    for right in range(1, len(prefix)):
        needed = prefix[right] - target
        left = bisect.bisect_right(prefix, needed, 0, right) - 1

        if left >= 0 and left < right:
            min_length = min(min_length, right - left)

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

print(minimum_size_subarray_sum_binary_search(7, [2, 3, 1, 2, 4, 3]))  # 2

C++

minimum_size_subarray_sum_binary_search.cpp

#include <iostream>
#include <vector>
#include <algorithm>

int minSubArrayLenBinarySearch(int target, std::vector<int>& nums) {
    std::vector<int> prefix;
    prefix.push_back(0);
    for (int num : nums) {
        prefix.push_back(prefix.back() + num);
    }

    int min_length = INT_MAX;

    for (int right = 1; right < (int)prefix.size(); right++) {
        int needed = prefix[right] - target;
        int left = std::upper_bound(prefix.begin(), prefix.begin() + right, needed) - prefix.begin() - 1;

        if (left >= 0 && left < right) {
            min_length = std::min(min_length, right - left);
        }
    }

    return min_length == INT_MAX ? 0 : min_length;
}

int main() {
    std::vector<int> nums = {2, 3, 1, 2, 4, 3};
    int target = 7;
    int result = minSubArrayLenBinarySearch(target, nums);
    std::cout << result << std::endl;
    return 0;
}

Java

minimum_size_subarray_sum_binary_search.java

import java.util.Arrays;

public class Main {
    public static int minSubArrayLenBinarySearch(int target, int[] nums) {
        int[] prefix = new int[nums.length + 1];
        prefix[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        int minLength = Integer.MAX_VALUE;

        for (int right = 1; right < prefix.length; right++) {
            int needed = prefix[right] - target;
            int left = binarySearchRightmost(prefix, needed, 0, right) - 1;

            if (left >= 0 && left < right) {
                minLength = Math.min(minLength, right - left);
            }
        }

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

    private static int binarySearchRightmost(int[] prefix, int target, int lo, int hi) {
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (prefix[mid] <= target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 2, 4, 3};
        int target = 7;
        int result = minSubArrayLenBinarySearch(target, nums);
        System.out.println(result);
    }
}

JavaScript

minimum_size_subarray_sum_binary_search.js

function minSubArrayLenBinarySearch(target, nums) {
    const prefix = [0];
    for (let num of nums) {
        prefix.push(prefix[prefix.length - 1] + num);
    }

    let minLength = Infinity;

    for (let right = 1; right < prefix.length; right++) {
        const needed = prefix[right] - target;
        const left = binarySearchRightmost(prefix, needed, 0, right) - 1;

        if (left >= 0 && left < right) {
            minLength = Math.min(minLength, right - left);
        }
    }

    return minLength === Infinity ? 0 : minLength;
}

function binarySearchRightmost(arr, target, lo, hi) {
    while (lo < hi) {
        const mid = Math.floor(lo + (hi - lo) / 2);
        if (arr[mid] <= target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

const nums = [2, 3, 1, 2, 4, 3];
const target = 7;
const result = minSubArrayLenBinarySearch(target, nums);
console.log(result);  // 2

Rust

minimum_size_subarray_sum_binary_search.rs

fn min_sub_array_len_binary_search(target: i32, nums: &[i32]) -> i32 {
    let mut prefix = vec![0];
    for &num in nums {
        prefix.push(prefix[prefix.len() - 1] + num);
    }

    let mut min_length = i32::MAX;

    for right in 1..prefix.len() {
        let needed = prefix[right] - target;
        let left_pos = binary_search_rightmost(&prefix, needed, 0, right);
        let left = if left_pos > 0 { left_pos - 1 } else { 0 };

        if left < right {
            min_length = min_length.min((right - left) as i32);
        }
    }

    if min_length == i32::MAX { 0 } else { min_length }
}

fn binary_search_rightmost(arr: &[i32], target: i32, lo: usize, hi: usize) -> usize {
    let mut lo = lo;
    let mut hi = hi;
    while lo < hi {
        let mid = lo + (hi - lo) / 2;
        if arr[mid] <= target {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    lo
}

fn main() {
    let nums = vec![2, 3, 1, 2, 4, 3];
    let target = 7;
    let result = min_sub_array_len_binary_search(target, &nums);
    println!("{}", result);  // 2
}

Go

minimum_size_subarray_sum_binary_search.go

package main

import (
  "fmt"
  "sort"
)

func minSubArrayLenBinarySearch(target int, nums []int) int {
  prefix := []int{0}
  for _, num := range nums {
    prefix = append(prefix, prefix[len(prefix)-1]+num)
  }

  minLength := int(^uint(0) >> 1)

  for right := 1; right < len(prefix); right++ {
    needed := prefix[right] - target
    leftPos := binarySearchRightmost(prefix, needed, 0, right)
    left := leftPos - 1

    if left >= 0 && left < right {
      if right-left < minLength {
        minLength = right - left
      }
    }
  }

  if minLength == int(^uint(0)>>1) {
    return 0
  }
  return minLength
}

func binarySearchRightmost(arr []int, target int, lo int, hi int) int {
  result := sort.SearchInts(arr[lo:hi], target+1) + lo
  return result
}

func main() {
  nums := []int{2, 3, 1, 2, 4, 3}
  target := 7
  result := minSubArrayLenBinarySearch(target, nums)
  fmt.Println(result)  // 2
}

Common mistakes

Watch for these pitfalls

• Off-by-one errors in window length: Remember that length = right - left + 1, not right - left.
• Forgetting to return 0: If no subarray reaches the target, return 0, not -1 or an empty list.
• Comparing sum >= target, not >: The problem asks for sum >= target, not strictly greater.
• Not handling the shrink phase: In the sliding window, forgetting to update the minimum length before shrinking leads to wrong answers.
• Binary search bounds: Make sure the binary search finds the leftmost position where prefix sum is valid, not just any position.

Approach 3: Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

minimum_size_subarray_sum_optimized.py

"""
Solution for Minimum Size Subarray Sum
"""

def solve():
    """Implementation for approach 3 of Minimum Size Subarray Sum"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

minimum_size_subarray_sum_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Minimum Size Subarray Sum
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

MinimumSizeSubarraySumOptimized.java

/**
 * Solution for Minimum Size Subarray Sum
 * Approach 3
 */
public class MinimumSizeSubarraySumOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

minimum_size_subarray_sum_optimized.js

/**
 * Solution for Minimum Size Subarray Sum
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

minimum_size_subarray_sum_optimized.rs

/// Solution for Minimum Size Subarray Sum
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

minimum_size_subarray_sum_optimized.go

package main

import "fmt"

// Solution for Minimum Size Subarray Sum
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Longest Substring Without Repeating Characters ↗ Medium #3
• Minimum Window Substring ↗ Hard #76
• Maximum Size Subarray Sum Equals k ↗ Medium #325
• Shortest Subarray with Sum at Least K ↗ Hard #862

Interview Tips

Key trade-offs to discuss

• Why sliding window over binary search? It achieves O(n) time with O(1) space, the optimal result. Binary search is O(n log n) with O(n) space, slower but demonstrates algorithmic thinking.
• Edge case: all numbers smaller than target — The function correctly returns 0.
• Positive integers guarantee — Since all numbers are positive, the sliding window never “backtracks.” Once the sum is large enough, removing elements only makes it smaller.
• Follow-up: what if numbers can be negative? The sliding window approach breaks because removing a negative number could increase the sum. You’d need a different strategy (e.g., prefix sum + hash map, or deque-based approach).

← Previous
#11 Container With Most Water Next
#30 Substring with Concatenation of All Words →