algoadvance

Leetcode 209. Minimum Size Subarray Sum

Problem Statement

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [nums[l], nums[l+1], ..., nums[r-1]] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

Clarifying Questions

  1. Are all elements in the array positive integers?
    • Yes, all elements are positive integers.
  2. Can the array have duplicate elements?
    • Yes, the array can have duplicate elements.
  3. Is the target always a positive integer?
    • Yes, the target is always a positive integer.
  4. What are the constraints on the size of the array?
    • The length of the array (n) can be up to 10^5 and the value of each element in the array can be up to 10^4.

Strategy

We can solve this problem using the sliding window (or two-pointer) technique:

  1. Initialize Two Pointers: Start with two pointers, left and right, both at the beginning of the array.
  2. Move the Right Pointer: Expand the window by moving the right pointer to the right and adding the elements to current_sum until current_sum becomes greater than or equal to target.
  3. Move the Left Pointer: When current_sum is greater than or equal to target, move the left pointer to the right to shrink the window. After each move, update the minimum length of the subarray and subtract the element at left from current_sum.
  4. Repeat until the right pointer reaches the end of the array.
  5. Edge Case: If no valid subarray is found, return 0.

Code

public class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int left = 0;
        int currentSum = 0;
        int minLength = Integer.MAX_VALUE;

        for (int right = 0; right < n; right++) {
            currentSum += nums[right];

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

        return (minLength == Integer.MAX_VALUE) ? 0 : minLength;
    }
}

Time Complexity

This sliding window approach is efficient and suitable for the input constraints given in the problem.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI