Smallest Subarray With Sum at Least Target

medium array sliding window

Problem

For an array of positive numbers, return the length of the shortest contiguous subarray whose sum is at least target, or 0 if no such subarray exists. Slide a window: extend the right edge, adding to a running sum. The moment the sum reaches the target, contract the left edge as much as possible while still meeting the target — at each shrink, the window is the shortest valid window ending at the current right index.

Inputtarget = 7, nums = [2, 3, 1, 2, 4, 3]

Output2

Window [4, 3] has sum 7. No single element reaches 7.

nums (positive, comma-separated)

target

def min_sub_array_len(target, nums):
    l = sum_ = 0
    best = float("inf")
    for r in range(len(nums)):
        sum_ += nums[r]
        while sum_ >= target:
            best = min(best, r - l + 1)
            sum_ -= nums[l]
            l += 1
    return 0 if best == float("inf") else best

function minSubArrayLen(target, nums) {
  let l = 0, sum = 0, best = Infinity;
  for (let r = 0; r < nums.length; r++) {
    sum += nums[r];
    while (sum >= target) {
      best = Math.min(best, r - l + 1);
      sum -= nums[l++];
    }
  }
  return best === Infinity ? 0 : best;
}

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int l = 0, sum = 0, best = Integer.MAX_VALUE;
        for (int r = 0; r < nums.length; r++) {
            sum += nums[r];
            while (sum >= target) {
                best = Math.min(best, r - l + 1);
                sum -= nums[l++];
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }
}

int minSubArrayLen(int target, vector<int>& nums) {
    int l = 0, sum = 0, best = INT_MAX;
    for (int r = 0; r < (int)nums.size(); r++) {
        sum += nums[r];
        while (sum >= target) {
            best = min(best, r - l + 1);
            sum -= nums[l++];
        }
    }
    return best == INT_MAX ? 0 : best;
}

Time: O(n) Space: O(1)