209, Minimum Size Subarray Sum

Mike10/12/23About 4 min

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

Related Topics:

array
binary search
sliding window
prefix sum

II Solution

Approach 1: Brute Force

Rust

/// Time Limit Exceeded
///
/// Time Complexity: O(n^3)
/// Space complexity: O(1)
pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
    let len = nums.len();

    for width in 1..=len {
        let mut begin = 0;
        let mut end = width;

        while end <= len {
            let mut sum = 0;
            for i in begin..end {
                sum += nums[i];
            }

            if sum >= target {
                return width as i32;
            }
            begin += 1;
            end = begin + width;
        }
    }

    0
}

Java

public int minSubArrayLen(int target, int[] nums) {
    for (int width = 1; width <= nums.length; width++) {
        int begin = 0;
        int end = width;

        while (end <= nums.length) {
            int sum = 0;
            for (int i = begin; i < end; i++) {
                sum += nums[i];
            }
            if (sum >= target) {
                return width;
            }

            begin++;
            end = begin + width;
        }
    }

    return 0;
}

func minSubArrayLen(target int, nums []int) int {
    size := len(nums)

    for width := 1; width <= size; width++ {
        beg, end := 0, width

        for end <= size {
            sum := 0
            for i := beg; i < end; i++ {
                sum += nums[i]
            }
            if sum >= target {
                return width
            }

            beg++
            end = beg + width
        }
    }

    return 0
}

public int MinSubArrayLen(int target, int[] nums)
{
    for (int width = 1; width <= nums.Length; width++)
    {
        int beg = 0;
        int end = width;
        while (end <= nums.Length)
        {
            int sum = 0;
            for (int i = beg; i < end; i++)
                sum += nums[i];
            if (sum >= target)
                return width;

            beg++;
            end = beg + width;
        }
    }
    
    return 0;
}

C++

int minSubArrayLen(int target, vector<int>& nums) {
    auto size = nums.size();

    for (auto width = 1; width <= size; ++width) {
        auto[beg, end] = std::make_pair(0, width);
        while (end <= size) {
            auto sum = 0;
            for (auto i = beg; i < end; ++i)
                sum += nums[i];

            if (sum >= target)
                return width;
            ++beg;
            end = beg + width;
        }
    }

    return 0;
}

Approach 2: Using Binary Search

Rust

/// Time complexity: O(n*log(n))
///
/// Space complexity: O(n)
pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
    let len = nums.len();
    let mut res = usize::MAX;
    let mut sums = vec![0; len + 1];

    for i in 0..len {
        sums[i + 1] = sums[i] + nums[i];
    }

    for i in 0..len {
        let to_find = target + sums[i];
        let idx = sums.binary_search(&to_find).unwrap_or_else(|idx| idx);
        if idx <= len {
            res = std::cmp::min(res, idx - i);
        }
    }

    if res != usize::MAX {
        res as i32
    } else {
        0
    }
}

Java

public int minSubArrayLen(int target, int[] nums) {
    int res = Integer.MAX_VALUE;
    int[] sums = new int[nums.length + 1];

    for (int i = 0; i < nums.length; i++) {
        sums[i + 1] = sums[i] + nums[i];
    }
    for (int i = 0; i < nums.length; i++) {
        int toFind = target + sums[i];
        int idx = Arrays.binarySearch(sums, toFind);
        idx = idx < 0 ? Math.abs(idx) - 1 : idx;
        if (idx <= nums.length) {
            res = Math.min(res, idx - i);
        }
    }

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

import (
    "math"
    "slices"
)

func minSubArrayLen(target int, nums []int) int {
    size := len(nums)
    res := math.MaxInt
    sums := make([]int, size+1)

    for i := 0; i < size; i++ {
        sums[i+1] = sums[i] + nums[i]
    }

    for i := 0; i < size; i++ {
        toFind := target + sums[i]
        idx, _ := slices.BinarySearch(sums, toFind)
        if idx <= size {
            res = min(res, idx-i)
        }
    }

    if res != math.MaxInt {
        return res
    }
    return 0
}

public int MinSubArrayLen(int target, int[] nums)
{
    int res = Int32.MaxValue;
    int[] sums = new int[nums.Length + 1];

    for (int i = 0; i < nums.Length; i++)
        sums[i + 1] = sums[i] + nums[i];

    for (int i = 0; i < nums.Length; i++)
    {
        int toFind = target + sums[i];
        int idx = Array.BinarySearch(sums, toFind);
        if (idx < 0)
            idx = Math.Abs(idx) - 1;
        if (idx <= nums.Length)
            res = Math.Min(res, idx - i);
    }

    return res == Int32.MaxValue ? 0 : res;
}

C++

#include <cstdint>

int minSubArrayLen(int target, vector<int>& nums) {
    const auto size = nums.size();
    int res = INT32_MAX;
    vector<int> sums(size + 1);

    for (auto i = 0; i < size; ++i)
        sums[i + 1] = sums[i] + nums[i];

    for (auto i = 0; i < size; ++i) {
        auto to_find = sums[i] + target;
        auto idx = std::lower_bound(sums.cbegin(), sums.cend(), to_find) - sums.begin();
        if (idx <= size)
            res = std::min(res, static_cast<int>(idx - i));
    }

    return res == INT32_MAX ? 0 : res;
}

Approach 3: Sliding Window

Rust

/// Time complexity: O(n)
///
/// Space complexity: O(1)
pub fn min_sub_array_len(target: i32, nums: Vec<i32>) -> i32 {
    let len = nums.len();
    let mut res = usize::MAX;
    let mut left = 0;
    let mut sum = 0;

    for i in 0..len {
        sum += nums[i];
        while sum >= target {
            res = std::cmp::min(res, i + 1 - left);
            sum -= nums[left];
            left += 1;
        }
    }

    if res == usize::MAX {
        0
    } else {
        res as i32
    }
}

Java

public int minSubArrayLen(int target, int[] nums) {
    int res = Integer.MAX_VALUE;
    int left = 0;
    int sum = 0;

    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        while (sum >= target) {
            res = Math.min(res, i + 1 - left);
            sum -= nums[left];
            ++left;
        }
    }

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

import "math"

func minSubArrayLen(target int, nums []int) int {
    size := len(nums)
    res := math.MaxInt
    left := 0
    sum := 0

    for i := 0; i < size; i++ {
        sum += nums[i]
        for sum >= target {
            res = min(res, i-left+1)
            sum -= nums[left]
            left++
        }
    }

    if res != math.MaxInt {
        return res
    }
    return 0
}

public int MinSubArrayLen(int target, int[] nums)
{
    int res = Int32.MaxValue;
    int left = 0;
    int sum = 0;

    for (int i = 0; i < nums.Length; i++)
    {
        sum += nums[i];
        while (sum >= target)
        {
            res = Math.Min(res, i - left + 1);
            sum -= nums[left];
            ++left;
        }
    }

    return res == Int32.MaxValue ? 0 : res;
}

C++

#include <cstdint>

int minSubArrayLen(int target, vector<int>& nums) {
    const auto size = nums.size();
    int res = INT32_MAX;
    int left = 0, sum = 0;

    for (auto i = 0; i < size; ++i) {
        sum += nums[i];
        while (sum >= target) {
            res = std::min(res, i - left + 1);
            sum -= nums[left];
            ++left;
        }
    }

    return res == INT32_MAX ? 0 : res;
}