Minimum Size Subarray Sum Visualizer: Shrinkable Sliding Window

Minimum Size Subarray Sum: how it works

1. Shrinkable Sliding Window

   Use two pointers (left, right). Expand right to grow the window and accumulate sum. Once sum ≥ target, try shrinking from the left to minimize window length.

2. Shrink while valid

   While sum ≥ target: record current window length as a candidate for the minimum, then remove the leftmost element and advance left. This ensures we find the shortest window.

3. Why O(N)?

   Each element is added at most once (right pointer) and removed at most once (left pointer). So the total operations across all iterations is O(2N) = O(N).

4. Binary Search Alternative

   There is also an O(N log N) approach: build prefix sums, then for each index i binary search for the smallest j ≥ i such that prefix[j] − prefix[i] ≥ target. The O(N) sliding window is strictly better.

Complexity

Best-case time

O(N)

Average time

O(N)

Worst-case time

O(N)

Space

O(1)

Works only for arrays with positive integers. For negative numbers, use prefix sums + monotonic deque (LeetCode 862).