maw.sh > Mahmoud Ashraf Website

SupportPalestine

209. Minimum Size Subarray Sum 🔗

Date: Jun 02, 2024

Tags: two-pointers, sliding-window

Description

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 <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104

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

Optimal

function minSubArrayLen(target: number = 0, nums: number[]): number {
  let left = 0;
  let total = 0;
  let result = Infinity;

  for (let right = 0; right < nums.length; right++) {
    total += nums[right];

    while (total >= target) {
      result = Math.min(result, right - left + 1);
      total -= nums[left];
      left++;
    }
  }

  return result === Infinity ? 0 : result;
}

export { minSubArrayLen };

Brute-Force

function minSubArrayLen(target: number, nums: number[]): number {
  const answers: number[] = [];

  for (let x = 0; x < nums.length; x++) {
    let acc = 0;

    for (let y = x; y < nums.length; y++) {
      if (x === y) acc = nums[x];
      else acc += nums[y];

      if (acc >= target) {
        answers.push(Math.abs(y - x) + 1);
        break;
      }
    }
  }

  return answers.length ? Math.min(...answers) : 0;
}

export { minSubArrayLen };