LEETCODE 209 (OPTIMIZED) • TWO POINTERS
Minimum Size Subarray Sum
MEDIUM • $O(N)$ GOOGLE BENCHMARK
Given an array of positive integers nums and a target target, return the minimal length of a contiguous subarray of which the sum is greater than or equal to target. If there is no such subarray, return 0.
📐 Mathematical Invariant & Proof
The Sliding Window Monotonicity Invariant:
Because all elements $nums[i] \ge 0$, expanding $right$ monotonically increases window sum. When $sum \ge target$, contracting $left$ monotonically decreases sum. Thus, both $left$ and $right$ advance at most $N$ times, proving optimal $\mathcal{O}(N)$ time complexity and avoiding the naive $\mathcal{O}(N^2)$ brute force.
Because all elements $nums[i] \ge 0$, expanding $right$ monotonically increases window sum. When $sum \ge target$, contracting $left$ monotonically decreases sum. Thus, both $left$ and $right$ advance at most $N$ times, proving optimal $\mathcal{O}(N)$ time complexity and avoiding the naive $\mathcal{O}(N^2)$ brute force.
🌐 Google Production System Design
Google Cloud Armor DDoS Rate Limiting:
Sliding window counters are deployed in Envoy proxies protecting upstream microservices. By tracking rolling window increments in high-throughput distributed memory (Redis cluster with Lua scripts), requests exceeding quota within window $W$ are throttled with HTTP 429 in sub-millisecond latency without lock contention.
Sliding window counters are deployed in Envoy proxies protecting upstream microservices. By tracking rolling window increments in high-throughput distributed memory (Redis cluster with Lua scripts), requests exceeding quota within window $W$ are throttled with HTTP 429 in sub-millisecond latency without lock contention.
💡 Hint 1: Visual Intuition & Mental Model
▼
Think of the window like a caterpillar crawling across the array. The head (right pointer) stretches forward adding elements to the sum. Once the target threshold is met or exceeded, the tail (left pointer) contracts to discover the tightest possible valid span.
🔍 Hint 2: Invariants & State Transitions
▼
Maintain:
currentSum and minLen = Infinity.
Outer loop advances right from 0 to N-1.
Inner loop runs while (currentSum >= target):
update minLen = Math.min(minLen, right - left + 1), subtract nums[left++].
⭐ Hint 3: Optimal Reference Code
▼
function maxSubarraySum(target, nums) {
let minLen = Infinity, sum = 0, left = 0;
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
minLen = Math.min(minLen, right - left + 1);
sum -= nums[left++];
}
}
return minLen === Infinity ? 0 : minLen;
}
⚡ Visual Algorithmic State Tracer (Step 1 / 12)
LEFT POINTER
0
RIGHT POINTER
0
WINDOW SUM
2
OPTIMAL MIN LEN
∞
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Run tests to evaluate latency & correctness
INPUT ARGUMENTS
target = 7, nums = [2, 3, 1, 2, 4, 3]
EXPECTED OUTPUT
2
ACTUAL OUTPUT
Pending Run
Execution latency: pending execution