# 209. Minimum Size Subarray Sum

LeetCode Problem Link (opens new window)

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray for which the sum is greater than or equal to s. If there isn’t one, return 0 instead.

Example:

  • Input: s = 7, nums = [2,3,1,2,4,3]
  • Output: 2
  • Explanation: The subarray [4,3] has the minimal length under the problem constraints.

Constraints:

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

# Solution

# Brute Force Solution

The brute force solution involves two nested for loops to continually search for subarrays that meet the desired condition. The time complexity is obviously O(n^2).

Here is the code:

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX; // the final result
        int sum = 0; // sum of the subarray
        int subLength = 0; // length of the subarray
        for (int i = 0; i < nums.size(); i++) { // set the starting point of the subarray as i
            sum = 0;
            for (int j = i; j < nums.size(); j++) { // set the endpoint of the subarray as j
                sum += nums[j];
                if (sum >= s) { // once the sum exceeds s, update the result
                    subLength = j - i + 1; // take the subarray length
                    result = min(result, subLength);
                    break; // since we are looking for the shortest subarray that meets the conditions, we break once we find one
                }
            }
        }
        // if result hasn't been assigned, return 0, indicating no such subarray exists
        return result == INT32_MAX ? 0 : result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
  • Time Complexity: O(n^2)
  • Space Complexity: O(1)

With the update of data on LeetCode, the brute force solution has timed out.

# Sliding Window

Next, we introduce another important method for array operations: Sliding Window.

The sliding window approach involves continuously adjusting the starting and ending positions of the subarray until we get the desired result.

In the brute force solution, a for loop represents the starting position of the sliding window and another for loop represents the ending position. This forms a continuous search through the intervals.

How can we use a single for loop to accomplish this operation?

First, think about whether a single for loop should represent the starting or ending position of the sliding window. If it represents only the starting position, how do we traverse the remaining ending positions?

This can easily lead to the trap of a brute force solution.

So if using a single for loop, the index must represent the ending position of the sliding window.

But how then do we move the starting position of the sliding window?

Let's walk through the example provided in the problem statement with s=7 and the array 2, 3, 1, 2, 4, 3 to understand the process:

209.Minimum Size Subarray

Ultimately, we find that [4, 3] is the shortest subarray that meets the requirement.

From the animation, you can see the sliding window can also be understood as a type of double-pointer approach! However, since this method resembles a window's movement, it's more appropriate to call it a sliding window.

In this problem, to implement a sliding window, primarily determine the following three points:

  • What is within the window?
  • How does the window's starting position move?
  • How does the window's ending position move?

The window is the smallest contiguous subarray with a sum ≥ s.

The starting position of the window moves when the current window's sum exceeds s (i.e., it should be reduced).

The ending position of the window is just the index traversed by the array, i.e., the index in the for loop.

The key to solving this problem lies in how the starting position of the window moves, as shown in the diagram:

leetcode_209

It can be seen that the highlight of the sliding window is in continuously adjusting the starting position according to the current subarray sum, thereby reducing the O(n^2) brute force solution to O(n).

Here's the C++ code:

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // sum of the sliding window
        int i = 0; // start of the sliding window
        int subLength = 0; // length of the sliding window
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // Use while here to continuously update i (starting position) and check if the subarray meets the criteria
            while (sum >= s) {
                subLength = (j - i + 1); // take the length of the subarray
                result = min(result, subLength);
                sum -= nums[i++]; // This demonstrates the elegance of the sliding window approach, continuously adjusting i (starting position of the subarray)
            }
        }
        // If result hasn't been assigned, return 0, indicating no such subarray exists
        return result == INT32_MAX ? 0 : result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
  • Time Complexity: O(n)
  • Space Complexity: O(1)

Some might wonder why the time complexity is O(n).

Don't assume it's O(n^2) just because there's a while within a for — mainly observe how many times each element is operated on. Every element is added to the sliding window once and removed once, so each element is operated on twice. Therefore, the time complexity is 2 × n, which is O(n).

# Implementations in Other Languages

# Java:

class Solution {
    // Sliding window
    public int minSubArrayLen(int s, int[] nums) {
        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= s) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# Python:

# Version 1: Sliding Window
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        l = len(nums)
        left = 0
        right = 0
        min_len = float('inf')
        cur_sum = 0 # current accumulated value
        
        while right < l:
            cur_sum += nums[right]
            while cur_sum >= s: # current accumulated value exceeds target
                min_len = min(min_len, right - left + 1)
                cur_sum -= nums[left]
                left += 1
            right += 1
        
        return min_len if min_len != float('inf') else 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Version 2: Brute Force
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        l = len(nums)
        min_len = float('inf')
        
        for i in range(l):
            cur_sum = 0
            for j in range(i, l):
                cur_sum += nums[j]
                if cur_sum >= s:
                    min_len = min(min_len, j - i + 1)
                    break
        
        return min_len if min_len != float('inf') else 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# Go:

func minSubArrayLen(target int, nums []int) int {
    i := 0
    l := len(nums)  // Length of the array
    sum := 0        // Sum of the subarray
    result := l + 1 // Initialize the length of the returned subarray to be l+1 to handle the case when there is no subarray that meets the criteria
    for j := 0; j < l; j++ {
        sum += nums[j]
        while sum >= target {
            subLength := j - i + 1
            if subLength < result {
                result = subLength
            }
            sum -= nums[i]
            i++
        }
    }
    if result == l+1 {
        return 0
    } else {
        return result
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# JavaScript:

var minSubArrayLen = function(target, nums) {
    let start, end
    start = end = 0
    let sum = 0
    let len = nums.length
    let ans = Infinity
    
    while(end < len){
        sum += nums[end];
        while (sum >= target) {
            ans = Math.min(ans, end - start + 1);
            sum -= nums[start];
            start++;
        }
        end++;
    }
    return ans === Infinity ? 0 : ans
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# TypeScript:

function minSubArrayLen(target: number, nums: number[]): number {
  let left: number = 0,
    res: number = Infinity,
    subLen: number = 0,
    sum: number = 0;
  for (let right: number = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum >= target) {
      subLen = right - left + 1;
      res = Math.min(res, subLen);
      sum -= nums[left];
      left++;
    }
  }
  return res === Infinity ? 0 : res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# Swift:

func minSubArrayLen(_ target: Int, _ nums: [Int]) -> Int {
    var result = Int.max
    var sum = 0
    var starIndex = 0
    for endIndex in 0..<nums.count {
        sum += nums[endIndex]

        while sum >= target {
            result = min(result, endIndex - starIndex + 1)
            sum -= nums[starIndex]
            starIndex += 1
        }
    }

    return result == Int.max ? 0 : result
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# Rust:

impl Solution {
    pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
        let (mut result, mut subLength): (i32, i32) = (i32::MAX, 0);
        let (mut sum, mut i) = (0, 0);

        for (pos, val) in nums.iter().enumerate() {
            sum += val;
            while sum >= target {
                subLength = (pos - i + 1) as i32;
                if result > subLength {
                    result = subLength;
                }
                sum -= nums[i];
                i += 1;
            }
        }
        if result == i32::MAX {
            return 0;
        }
        result
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# PHP:

// Two Pointers - Sliding Window
class Solution {
    /**
     * @param Integer $target
     * @param Integer[] $nums
     * @return Integer
     */
    function minSubArrayLen($target, $nums) {
        if (count($nums) < 1) {
            return 0;
        }
        $sum = 0;
        $res = PHP_INT_MAX;
        $left = 0;
        for ($right = 0; $right < count($nums); $right++) {
            $sum += $nums[$right];
            while ($sum >= $target) {
                $res = min($res, $right - $left + 1);
                $sum -= $nums[$left];
                $left++;
            }
        }
        return $res == PHP_INT_MAX ? 0 : $res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# Ruby:

def min_sub_array_len(target, nums)
  res = Float::INFINITY # Infinity
  i, sum = 0, 0
  nums.length.times do |j|
    sum += nums[j]
    while sum >= target
      res = [res, j - i + 1].min
      sum -= nums[i]
      i += 1
    end
  end
  res == Float::INFINITY ? 0 : res
end
1
2
3
4
5
6
7
8
9
10
11
12
13

# C:

Brute force solution:

int minSubArrayLen(int target, int* nums, int numsSize){
    // Initialize the minimum length as INT_MAX
    int minLength = INT_MAX;
    int sum;

    int left, right;
    for(left = 0; left < numsSize; ++left) {
        // Reset sum to zero for each iteration to calculate the length of subarrays starting from the current position
        sum = 0;
        // Add elements to sum starting from left
        for(right = left; right < numsSize; ++right) {
            sum += nums[right];
            // If adding the current element makes the sum exceed the target, update minLength
            if(sum >= target) {
                int subLength = right - left + 1;
                minLength = min(minLength, subLength);
                break;
            }
        }
    }
    // Return 0 if minLength remains INT_MAX, otherwise return minLength
    return minLength == INT_MAX ? 0 : minLength;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Sliding window:

int minSubArrayLen(int target, int* nums, int numsSize){
    // Initialize the minimum length as INT_MAX
    int minLength = INT_MAX;
    int sum = 0;

    int left = 0, right = 0;
    // Right boundary moves to the right
    for(; right < numsSize; ++right) {
        sum += nums[right];
        // When sum is greater than or equal to target, save the length and shrink the left boundary
        while(sum >= target) {
            int subLength = right - left + 1;
            minLength = min(minLength, subLength);
            sum -= nums[left++];
        }
    }
    // Return 0 if minLength remains INT_MAX, otherwise return minLength
    return minLength == INT_MAX ? 0 : minLength;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# Kotlin:

class Solution {
    fun minSubArrayLen(target: Int, nums: IntArray): Int {
        var start = 0
        var end = 0
        var ret = Int.MAX_VALUE
        var count = 0
        while (end < nums.size) {
            count += nums[end]
            while (count >= target) {
                ret = if (ret > (end - start + 1)) end - start + 1 else ret
                count -= nums[start++]
            }
            end++
        }
        return if (ret == Int.MAX_VALUE) 0 else ret
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Sliding window:

class Solution {
   fun minSubArrayLen(target: Int, nums: IntArray): Int {
    // Left and right boundaries
    var left: Int = 0
    var right: Int = 0
    // sum keeps track of the total sum
    var sum: Int = 0
    // result keeps a fixed value, easy to determine if such an array exists
    var result: Int = Int.MAX_VALUE
    // subLenth keeps the length
    var subLength = Int.MAX_VALUE
   

    while (right < nums.size) {
        // Start adding from the first element
        sum += nums[right++]
        // Check
        while (sum >= target) {
            var temp = right - left 
            // Compare with the last value each time to find the shortest length
            subLength = if (subLength > temp) temp else subLength
            // Reduce sum, move the left boundary right
            sum -= nums[left++]
        }
    }
    // Return 0 if subLength is the initial value, otherwise return subLength
    return if(subLength == result) 0 else subLength
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

# Scala:

Sliding window:

object Solution {
  def minSubArrayLen(target: Int, nums: Array[Int]): Int = {
    var result = Int.MaxValue // Infinite
    var left = 0 // slow pointer, move right when sum >= target
    var sum = 0 // sum of the window
    for (right <- 0 until nums.length) {
      sum += nums(right)
      while (sum >= target) {
        result = math.min(result, right - left + 1) // generate new result
        sum -= nums(left) // left pointer moves, reduce window sum
        left += 1 // left pointer moves right
      }
    }
    // Similar to a ternary operator, the return keyword can be discarded
    if (result == Int.MaxValue) 0 else result
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Brute force:

object Solution {
  def minSubArrayLen(target: Int, nums: Array[Int]): Int = {
    import scala.util.control.Breaks
    var res = Int.MaxValue
    var subLength = 0
    for (i <- 0 until nums.length) {
      var sum = 0
      Breaks.breakable(
        for (j <- i until nums.length) {
          sum += nums(j)
          if (sum >= target) {
            subLength = j - i + 1
            res = math.min(subLength, res)
            Breaks.break()
          }
        }
      )
    }
    // Equivalent to a ternary operator
    if (res == Int.MaxValue) 0 else res
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# C#:

public class Solution {
    public int MinSubArrayLen(int s, int[] nums) {
        int n = nums.Length;
        int ans = int.MaxValue;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n)  {
            sum += nums[end];
            while (sum >= s) 
            {
                ans = Math.Min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == int.MaxValue ? 0 : ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Last updated:: 9/4/2025, 3:19:38 PM
Copyright © 2025 keetcoder