Minimum Size Subarray Sum – 209. LeetCode

The Minimum Size Subarray Sum problem asks us to find the smallest contiguous subarray whose sum is greater than or equal to a given integer target. If no such subarray exists, we return 0. This problem is common in array manipulation and sliding window techniques.

In simple terms, imagine you’re trying to minimize the number of consecutive items you need from an array to achieve a certain sum. This problem is about efficiently finding that smallest group of numbers.

Brute Force

public class MinimumSizeSubarraySum {
    public int MinSubArrayLen(int target, int[] nums) {
        int left = 0, sum = 0, minLength = int.MaxValue;

        for (int right = 0; right < nums.Length; right++) {
            sum += nums[right]; // Expand the window

            while (sum >= target) { // Shrink the window
                minLength = Math.Min(minLength, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }

        return minLength == int.MaxValue ? 0 : minLength;
    }
}

While this approach guarantees correctness, it is not efficient for large arrays, as it redundantly recalculates sums for overlapping subarrays.

Optimized Approach: Sliding Window

To improve efficiency, we use the sliding window technique. Instead of examining all subarrays, we maintain a dynamic window (range) that grows or shrinks as needed. This reduces the time complexity significantly.

• Maintains a window of elements in the array that satisfies the sum condition.

• Expands the window by moving the right pointer.

• Shrinks the window by moving the left pointer as soon as the condition is met.

    public class Solution {
        public int MinSubArrayLen(int target, int[] nums) {
            int minLength = int.MaxValue;
            int left = 0;
            int currentSum = 0;

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

                while (currentSum >= target) {
                    minLength = Math.Min(minLength, right - left + 1);
                    currentSum -= nums[left];
                    left++;
                }
            }
            return minLength == int.MaxValue ? 0 : minLength;
        }
    }

Line-By-Line Description

Step 1: Initialization

int left = 0, currentSum = 0, minLength = int.MaxValue;

• left: The starting index of the sliding window.
• sum: The running sum of elements in the current window.
• minLength: Tracks the smallest valid window size.

Step 2: Expand the Window

for (int right = 0; right < nums.length; right++) {
    currentSum += nums[right];
}

• Iterates through the array, expanding the window by adding the current element to sum.

Step 3: Shrink the Window

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

• If the currentSum meets or exceeds target, the subarray is valid.
• Update minLength: Compares current subarray length with minLength and updates it if the current subarray is smaller.
• Subtracts nums[left] from currentSum
• Moves the left pointer forward to reduce the window size.\

Step 4: Return

return minLength == int.MaxValue ? 0 : minLength;

• Check if minLength was updated from its initial value

Why This Code Works

This C# implementation uses the sliding window technique to efficiently find the smallest subarray that meets the target sum. By dynamically adjusting the window size, the algorithm achieves linear time complexity, making it scalable and optimal. Its clean logic and edge case handling make it adhere to LeetCode best practices.