The O(n) Club: Minimum Size Subarray Sum (How to Outsmart Prefix Sums on LeetCode 209)

The O(n) Club: Minimum Size Subarray Sum (How to Outsmart Prefix Sums on LeetCode 209)

⚡ TL;DR

Here’s the deal: given an array of positive integers and a target, find the smallest length of a contiguous subarray with sum at least the target. Don’t brute-force unless your CPU likes suffering.
Pro Java fix below:

// Sliding window O(n)
int minSubArrayLen(int target, int[] nums) {
    int left = 0, sum = 0, min = Integer.MAX_VALUE;
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum >= target) {
            min = Math.min(min, right - left + 1);
            sum -= nums[left++];
        }
    }
    return min == Integer.MAX_VALUE ? 0 : min;
}

🧠 How Devs Usually Mess This Up

Is your go-to move to try prefix sums and double for-loops? That’s adorable. Welcome to O(n²) performance hell, where your subarray checks are slower than a Monday standup. Also, a subarray is always contiguous. Don’t go cherry-picking values from different planets in the array and call it a subarray. Seriously.

🔍 What’s Actually Going On

Since numbers don’t go negative (think: only deposits, no withdrawals), adding to the window always increases the sum. This lets you expand right for more sum, then slide the left pointer up to shrink and find the shortest fit, just like closing VSCode tabs at 3am until you see daylight. This is why the sliding window is the answer. If you see negatives, just run. Or use another algorithm.

🛠️ PseudoCode

• Start: Set left = 0, sum = 0, minLen = Integer.MAX_VALUE (that’s max value, not your coffee order).
• Stretch right: For each right in the array:

  sum += nums[right];

• Shrink when possible: While sum >= target:

  minLen = Math.min(minLen, right - left + 1);
  sum -= nums[left++];

• Tidy up: If minLen never moved, return 0.

  return minLen == Integer.MAX_VALUE ? 0 : minLen;

💻 The Code

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

⚠️ Pitfalls, Traps & Runtime Smacks

• If anyone hands you an array with negatives, sliding window logic crumbles faster than stale cookies. Beware.
• Return 0 when no window fits. It’s not a trick question. No “-1”, no “last index minus first.” Zero. Nada.
• Don’t mix up subarrays (contiguous) with subsequences (choose-your-own-adventure). It may seem subtle, but it’ll fail your test cases loudly.
• This is a true O(n) pass—every element is visited at most twice, and you get O(1) space with only a couple of ints. Prefix sums? Not today, pal.

🧠 Interviewer Brain-Tattoo

When numbers are all positive, slide your window. When they aren’t, slide your resume to another problem.