Minimum Size Subarray Sum - Solution & Explanation

Q: Is Minimum Size Subarray Sum easy or hard?

Minimum Size Subarray Sum is classified as a Medium problem on LeetCode. The difficulty comes from recognizing that the array contains only positive numbers, which enables the sliding window optimization that reduces the brute force O(n²) approach to O(n).

Q: How to solve Minimum Size Subarray Sum in O(n)?

Use a sliding window with two pointers. Move the right pointer across the array while adding elements to a running sum. Whenever the sum becomes greater than or equal to the target, update the minimum window length and move the left pointer forward to shrink the window while maintaining the condition.

Q: What is the best approach for Minimum Size Subarray Sum?

The sliding window approach is the optimal solution. Because all array elements are positive, you can expand the window with a right pointer to increase the sum and shrink it with a left pointer to minimize the length once the sum reaches the target. This processes each element at most twice and runs in O(n) time with O(1) extra space.

Q: What data structure is used in Minimum Size Subarray Sum?

The core solution uses two pointers operating on an array to maintain a sliding window and a running sum. An alternative approach uses a prefix sum array combined with binary search to find the smallest valid ending index for each starting position.

Q: What is the time complexity of Minimum Size Subarray Sum?

The optimal sliding window solution runs in O(n) time and O(1) space. Each element is added to the running sum once and removed once as the window expands and contracts. A prefix-sum plus binary-search approach exists with O(n log n) time and O(n) space.

Q: Minimum Size Subarray Sum Python or Java solution approach?

Both Python and Java implementations typically use the sliding window pattern. Maintain two indices and a running sum, expand the right pointer through the array, and shrink the left pointer while the sum remains ≥ target. This produces a clean O(n) implementation in either language.

Q: Is Minimum Size Subarray Sum asked at Google, Amazon, or Meta?

Minimum Size Subarray Sum appears frequently in interview preparation lists and has been reported in interviews at companies like Amazon and Google. It tests recognition of the sliding window pattern and the ability to optimize brute force subarray scanning into a linear-time solution.

MediumArray Binary Search Sliding Window Prefix Sum30 min readAsked at: Amazon, Microsoft, Apple +15

Practice this problem

Problem Statement

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)).

Approach Overview

Problem Overview: Given an array of positive integers and a target value, find the minimum length of a contiguous subarray whose sum is greater than or equal to the target. If no such subarray exists, return 0. The challenge is minimizing the length while keeping the running sum ≥ target.

Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)

Check every possible starting index and expand the subarray to the right while maintaining a running sum. As soon as the sum becomes ≥ target, record the length and stop expanding that starting point. This approach uses nested loops and repeatedly recomputes partial sums. It works for small arrays but quickly becomes slow because the worst case evaluates nearly every subarray.

Approach 2: Sliding Window / Two Pointers (O(n) time, O(1) space)

The optimal solution uses the sliding window technique. Because all numbers are positive, expanding the right pointer always increases the sum, and shrinking the left pointer always decreases it. Maintain two pointers left and right with a running sum. Expand right until the sum ≥ target, then shrink from the left while the condition still holds to minimize the window size. Each element enters and leaves the window at most once, producing linear time complexity. This approach is the standard solution for array problems involving contiguous segments with positive numbers.

Approach 3: Binary Search on Prefix Sums (O(n log n) time, O(n) space)

Build a prefix sum array where prefix[i] stores the sum of the first i elements. For each starting index i, you need the smallest index j such that prefix[j] - prefix[i] ≥ target. Since the prefix array is strictly increasing with positive numbers, you can apply binary search to find that index efficiently. Compute the candidate subarray length j - i and track the minimum. This method is useful when you want a systematic approach using prefix sums, though it is slower than sliding window.

Recommended for interviews: The sliding window solution is the expected answer. Interviewers want to see that you recognize the positive-number constraint and convert the problem into a dynamic window that expands and contracts. Mentioning the brute force approach first demonstrates baseline reasoning, but implementing the O(n) sliding window shows strong algorithmic pattern recognition.

Approach 1: Sliding Window Approach

The Sliding Window approach keeps track of a window using two pointers and dynamically adjusts subarray boundaries to maintain valid subarrays with sums greater than or equal to the target.

1. Initialize two pointers, left and right, both set to the start of the array.

2. Use right to expand the window by including elements in the subarray until the sum is equal to or exceeds the target.

3. Once the sum reaches or exceeds the target, attempt to minimize the window from the left by incrementing left while ensuring the sum remains equal to or greater than the target.

In the C solution, we maintain a running sum of the elements included in the sliding window. We keep incrementing the right pointer to include elements into the subarray. Each time the sum equals or exceeds the target, we check for the minimal length of the valid subarray and decrement elements from the left, reducing the subarray size.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n) where n is the length of the array.

Space Complexity: O(1) because we use a constant amount of extra space.

Try this approach in the editor →

Approach 2: Binary Search on Prefix Sums

This approach uses prefix sums and binary search to find the minimal length of subarrays summing to the required target. It builds on the idea that the sum of elements from index i to j can be represented using prefix sums, allowing us to search for valid subarray boundaries efficiently.

1. Compute the prefix sums of the array, which helps us quickly calculate the sum of any subarray.

2. For each starting index, use binary search to find the smallest ending index such that the subarray sum equals or exceeds the target.

In this C solution, we utilize prefix sums and binary search to efficiently locate minimum subarray lengths that meet the target. After constructing the prefix sum array, binary search over this array finds boundaries within a subarray sum condition, reducing it to an efficient search problem.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n log n) due to binary searching for each possible start index.

Space Complexity: O(n) for the prefix sums array.

Try this approach in the editor →

Approach 3: Prefix Sum + Binary Search

First, we preprocess the prefix sum array s of the array nums, where s[i] represents the sum of the first i elements of the array nums. Since all elements in the array nums are positive integers, the array s is also monotonically increasing. Also, we initialize the answer ans = n + 1, where n is the length of the array nums.

Next, we traverse the prefix sum array s. For each element s[i], we can find the smallest index j that satisfies s[j] geq s[i] + target by binary search. If j leq n, it means that there exists a subarray that satisfies the condition, and we can update the answer, i.e., ans = min(ans, j - i).

Finally, if ans leq n, it means that there exists a subarray that satisfies the condition, return ans, otherwise return 0.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.

Code

Python Java C++Go TypeScript Rust C#

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Approach 4: Two Pointers

We can use two pointers j and i to maintain a window, where the sum of all elements in the window is less than target. Initially, j = 0, and the answer ans = n + 1, where n is the length of the array nums.

Next, the pointer i starts to move to the right from 0, moving one step each time. We add the element corresponding to the pointer i to the window and update the sum of the elements in the window. If the sum of the elements in the window is greater than or equal to target, it means that the current subarray satisfies the condition, and we can update the answer, i.e., ans = min(ans, i - j + 1). Then we continuously remove the element nums[j] from the window until the sum of the elements in the window is less than target, and then repeat the above process.

Finally, if ans leq n, it means that there exists a subarray that satisfies the condition, return ans, otherwise return 0.

The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the array nums.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Sliding Window Approach	Time Complexity: `O(n)` where n is the length of the array. Space Complexity: `O(1)` because we use a constant amount of extra space.
Binary Search on Prefix Sums	Time Complexity: `O(n log n)` due to binary searching for each possible start index. Space Complexity: `O(n)` for the prefix sums array.
Prefix Sum + Binary Search	—
Two Pointers	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Brute Force Enumeration	O(n²)	O(1)	Conceptual baseline or very small arrays
Sliding Window	O(n)	O(1)	Optimal approach when array elements are positive
Binary Search on Prefix Sums	O(n log n)	O(n)	When using prefix sums or demonstrating binary search technique

Video Solution

Minimum Size Subarray Sum - Leetcode 209 - Python • NeetCode • 144,428 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Size Subarray Sum easy or hard?

Minimum Size Subarray Sum is classified as a Medium problem on LeetCode. The difficulty comes from recognizing that the array contains only positive numbers, which enables the sliding window optimization that reduces the brute force O(n²) approach to O(n).

How to solve Minimum Size Subarray Sum in O(n)?

Use a sliding window with two pointers. Move the right pointer across the array while adding elements to a running sum. Whenever the sum becomes greater than or equal to the target, update the minimum window length and move the left pointer forward to shrink the window while maintaining the condition.

What is the best approach for Minimum Size Subarray Sum?

The sliding window approach is the optimal solution. Because all array elements are positive, you can expand the window with a right pointer to increase the sum and shrink it with a left pointer to minimize the length once the sum reaches the target. This processes each element at most twice and runs in O(n) time with O(1) extra space.

What data structure is used in Minimum Size Subarray Sum?

The core solution uses two pointers operating on an array to maintain a sliding window and a running sum. An alternative approach uses a prefix sum array combined with binary search to find the smallest valid ending index for each starting position.

What is the time complexity of Minimum Size Subarray Sum?

The optimal sliding window solution runs in O(n) time and O(1) space. Each element is added to the running sum once and removed once as the window expands and contracts. A prefix-sum plus binary-search approach exists with O(n log n) time and O(n) space.

Minimum Size Subarray Sum Python or Java solution approach?

Both Python and Java implementations typically use the sliding window pattern. Maintain two indices and a running sum, expand the right pointer through the array, and shrink the left pointer while the sum remains ≥ target. This produces a clean O(n) implementation in either language.

Is Minimum Size Subarray Sum asked at Google, Amazon, or Meta?

Minimum Size Subarray Sum appears frequently in interview preparation lists and has been reported in interviews at companies like Amazon and Google. It tests recognition of the sliding window pattern and the ability to optimize brute force subarray scanning into a linear-time solution.

Ready to solve this problem?

Practice Minimum Size Subarray Sum with our built-in code editor and test cases.

Practice on FleetCode

K Radius Subarray Averages

Maximum Length of Repeated Subarray

Problem Info

DifficultyMedium

Acceptance52.5%

Approaches4

Reading time30 min

Asked at

Amazon Microsoft Apple Goldman Sachs Meta

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Sliding Window Approach

Code

Complexity

Approach 2: Binary Search on Prefix Sums

Code

Complexity

Approach 3: Prefix Sum + Binary Search

Code

Approach 4: Two Pointers

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents