Minimum Size Subarray Sum solution and explanation
Infosys
Google
TCS
9 more videos on this problem
Minimum Size Subarray Sum - Leetcode 209 - PythonNeetCode · 12:30 · 144K views
LeetCode Minimum Size Subarray Sum Solution Explained - JavaNick White · 8:36 · 48K views
Minimum Size Subarray Sum (LeetCode 209) | Full solution with animations | Variable Sliding WindowNikhil Lohia · 17:23 · 30K views
Minimum Size Subarray Sum - Leetcode 209 - Sliding Window (Python)Greg Hogg · 6:37 · 16K views
LeetCode 209. Minimum Size Subarray SumHappy Coding · 12:30 · 1K views
Leetcode Problem 209: Minimum Size Subarray Sum Solution With CodeAlex Solves Algorithms · 9:08 · 1K views
Minimum Size Subarray Sum - LeetCode 209 - Coding Interview QuestionsOne Code Man · 5:30 · 1K views
Leetcode 209 - Minimum Size Subarray Sum JavaScriptChuck's Resume · 11:17 · 714 views
Minimum Size Subarray Sum (Leetcode Problem 209) Solution Explained - JavaHarVi · 5:59 · 567 views
Leetcode 209 - Minimum Size Subarray Sum (JAVA Solution Explained!)LC Bear · 8:58 · 328 views
The 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.
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 <= 1091 <= nums.length <= 1051 <= nums[i] <= 104
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.
def minSubArrayLen(target, nums):
left = 0
sum_ = 0
min_length = float('inf')
for right in range(len(nums)):
sum_ += nums[right]
while sum_ >= target:
min_length = min(min_length, right - left + 1)
sum_ -= nums[left]
left += 1
return 0 if min_length == float('inf') else min_length
# Example usage:
nums = [2, 3, 1, 2, 4, 3]
target = 7
print(minSubArrayLen(target, nums))public class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0, sum = 0, minLength = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
minLength = Math.min(minLength, right - left + 1);
sum -= nums[left++];
}
}
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {2, 3, 1, 2, 4, 3};
int target = 7;
System.out.println(sol.minSubArrayLen(target, nums));
}
}#include <iostream>
#include <vector>
#include <limits.h>
int minSubArrayLen(int target, std::vector<int>& nums) {
int left = 0, sum = 0, minLength = INT_MAX;
for (int right = 0; right < nums.size(); right++) {
sum += nums[right];
while (sum >= target) {
minLength = std::min(minLength, right - left + 1);
sum -= nums[left++];
}
}
return minLength == INT_MAX ? 0 : minLength;
}
int main() {
std::vector<int> nums = {2, 3, 1, 2, 4, 3};
int target = 7;
std::cout << minSubArrayLen(target, nums) << std::endl;
return 0;
}function minSubArrayLen(target, nums) {
let left = 0;
let sum = 0;
let minLength = Infinity;
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
minLength = Math.min(minLength, right - left + 1);
sum -= nums[left];
left++;
}
}
return minLength === Infinity ? 0 : minLength;
}
// Example usage
console.log(minSubArrayLen(7, [2, 3, 1, 2, 4, 3]));#include <stdio.h>
int minSubArrayLen(int target, int* nums, int numsSize) {
int left = 0, sum = 0, minLength = numsSize + 1;
for (int right = 0; right < numsSize; right++) {
sum += nums[right];
while (sum >= target) {
minLength = (right - left + 1) < minLength ? (right - left + 1) : minLength;
sum -= nums[left++];
}
}
return minLength == numsSize + 1 ? 0 : minLength;
}
int main() {
int nums[] = {2, 3, 1, 2, 4, 3};
int target = 7;
int length = minSubArrayLen(target, nums, 6);
printf("%d\n", length);
return 0;
}using System;
public class Solution {
public int MinSubArrayLen(int target, int[] nums) {
int left = 0, sum = 0, minLength = int.MaxValue;
for (int right = 0; right < nums.Length; right++) {
sum += nums[right];
while (sum >= target) {
minLength = Math.Min(minLength, right - left + 1);
sum -= nums[left++];
}
}
return minLength == int.MaxValue ? 0 : minLength;
}
public static void Main() {
int[] nums = {2, 3, 1, 2, 4, 3};
int target = 7;
Solution sol = new Solution();
Console.WriteLine(sol.MinSubArrayLen(target, nums));
}
}The Python solution uses a sliding window and two pointers to efficiently track and minimize subarray sums as needed, updating the sum dynamically while providing conditions to alter the window.
Time Complexity: O(n) because each element is iterated through once.
Space Complexity: O(1) as no additional data structures are used.
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.
import bisect
def minSubArrayLen(target, nums):
prefix_sum = [0]
for num in nums:
prefix_sum.append(prefix_sum[-1] + num)
min_length = float('inf')
for i in range(len(nums)):
to_find = target + prefix_sum[i]
bound = bisect.bisect_left(prefix_sum, to_find, lo=i+1)
if bound <= len(nums):
min_length = min(min_length, bound - i)
return 0 if min_length == float('inf') else min_length
# Example usage:
nums = [2, 3, 1, 2, 4, 3]
target = 7
print(minSubArrayLen(target, nums))import java.util.*;
public class Solution {
public int minSubArrayLen(int target, int[] nums) {
int[] prefixSum = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
int minLength = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
int toFind = target + prefixSum[i];
int bound = Arrays.binarySearch(prefixSum, i + 1, nums.length + 1, toFind);
if (bound < 0) {
bound = -(bound + 1);
}
if (bound <= nums.length) {
minLength = Math.min(minLength, bound - i);
}
}
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {2, 3, 1, 2, 4, 3};
int target = 7;
System.out.println(sol.minSubArrayLen(target, nums));
}
}#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
int minSubArrayLen(int target, std::vector<int>& nums) {
std::vector<int> prefixSum(nums.size() + 1, 0);
for (int i = 0; i < nums.size(); i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
int minLength = INT_MAX;
for (int i = 0; i < nums.size(); i++) {
int toFind = target + prefixSum[i];
auto bound = std::lower_bound(prefixSum.begin() + i + 1, prefixSum.end(), toFind);
if (bound != prefixSum.end()) {
minLength = std::min(minLength, static_cast<int>(bound - (prefixSum.begin() + i)));
}
}
return minLength == INT_MAX ? 0 : minLength;
}
int main() {
std::vector<int> nums = {2, 3, 1, 2, 4, 3};
int target = 7;
std::cout << minSubArrayLen(target, nums) << std::endl;
return 0;
}function minSubArrayLen(target, nums) {
let prefixSum = [0];
for (let i = 0; i < nums.length; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
let minLength = Infinity;
for (let i = 0; i < nums.length; i++) {
let toFind = target + prefixSum[i];
let left = i + 1, right = prefixSum.length;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (prefixSum[mid] >= toFind) right = mid;
else left = mid + 1;
}
if (left <= nums.length) {
minLength = Math.min(minLength, left - i);
}
}
return minLength === Infinity ? 0 : minLength;
}
console.log(minSubArrayLen(7, [2, 3, 1, 2, 4, 3]));#include <stdio.h>
#include <limits.h>
int binarySearch(int* prefixSum, int left, int right, int target) {
while (left < right) {
int mid = left + (right - left) / 2;
if (prefixSum[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
int minSubArrayLen(int target, int* nums, int numsSize) {
int* prefixSum = (int*)malloc((numsSize + 1) * sizeof(int));
prefixSum[0] = 0;
for (int i = 0; i < numsSize; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
int minLength = INT_MAX;
for (int i = 0; i < numsSize; i++) {
int toFind = target + prefixSum[i];
int bound = binarySearch(prefixSum, i + 1, numsSize + 1, toFind);
if (bound <= numsSize) {
minLength = (bound - i) < minLength ? (bound - i) : minLength;
}
}
free(prefixSum);
return minLength == INT_MAX ? 0 : minLength;
}
int main() {
int nums[] = {2, 3, 1, 2, 4, 3};
int target = 7;
int length = minSubArrayLen(target, nums, 6);
printf("%d\n", length);
return 0;
}using System;
public class Solution {
public int MinSubArrayLen(int target, int[] nums) {
int[] prefixSum = new int[nums.Length + 1];
for (int i = 0; i < nums.Length; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
int minLength = int.MaxValue;
for (int i = 0; i < nums.Length; i++) {
int toFind = target + prefixSum[i];
int bound = Array.BinarySearch(prefixSum, i + 1, nums.Length - i, toFind);
if (bound < 0)
bound = ~bound;
if (bound <= nums.Length) {
minLength = Math.Min(minLength, bound - i);
}
}
return minLength == int.MaxValue ? 0 : minLength;
}
public static void Main() {
int[] nums = {2, 3, 1, 2, 4, 3};
int target = 7;
Solution sol = new Solution();
Console.WriteLine(sol.MinSubArrayLen(target, nums));
}
}This Python algorithm takes advantage of prefix sums and bisect module for enforcing boundaries within the subarray to optimize search and calculation of result lengths.
Time Complexity: O(n log n) given repeated search operations.
Space Complexity: O(n) due to prefix sum construction.
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.
function minSubArrayLen(target: number, nums: number[]): number {
const n = nums.length;
const s: number[] = new Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
s[i + 1] = s[i] + nums[i];
}
let ans = n + 1;
const search = (x: number) => {
let l = 0;
let r = n + 1;
while (l < r) {
const mid = (l + r) >>> 1;
if (s[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
for (let i = 0; i <= n; ++i) {
const j = search(s[i] + target);
if (j <= n) {
ans = Math.min(ans, j - i);
}
}
return ans === n + 1 ? 0 : ans;
}func minSubArrayLen(target int, nums []int) int {
n := len(nums)
s := make([]int, n+1)
for i, x := range nums {
s[i+1] = s[i] + x
}
ans := n + 1
for i, x := range s {
j := sort.SearchInts(s, x+target)
if j <= n {
ans = min(ans, j-i)
}
}
if ans == n+1 {
return 0
}
return ans
}impl Solution {
pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
let n = nums.len();
let mut res = n + 1;
let mut sum = 0;
let mut i = 0;
for j in 0..n {
sum += nums[j];
while sum >= target {
res = res.min(j - i + 1);
sum -= nums[i];
i += 1;
}
}
if res == n + 1 {
return 0;
}
res as i32
}
}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.
function minSubArrayLen(target: number, nums: number[]): number {
const n = nums.length;
let [s, ans] = [0, n + 1];
for (let l = 0, r = 0; r < n; ++r) {
s += nums[r];
while (s >= target) {
ans = Math.min(ans, r - l + 1);
s -= nums[l++];
}
}
return ans > n ? 0 : ans;
}func minSubArrayLen(target int, nums []int) int {
l, n := 0, len(nums)
s, ans := 0, n+1
for r, x := range nums {
s += x
for s >= target {
ans = min(ans, r-l+1)
s -= nums[l]
l++
}
}
if ans > n {
return 0
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | Time Complexity: Space Complexity: |
| Binary Search on Prefix Sums | Time Complexity: Space Complexity: |
| Prefix Sum + Binary Search | – |
| Two Pointers | – |
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 |
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.