Minimum Size Subarray Sum

Minimum Size Subarray Sum

What is this problem about?

The Minimum Size Subarray Sum problem asks you to find the shortest contiguous subarray in a positive integer array whose sum is at least a given target. If no such subarray exists, return 0. This Minimum Size Subarray Sum interview question is one of the most important problems for mastering the variable-size sliding window technique, and it appears on interview lists at nearly every major tech company.

Why is this asked in interviews?

This problem is asked by Apple, Google, Amazon, Meta, Microsoft, Bloomberg, Goldman Sachs, and many more companies because it is the canonical example of the variable sliding window interview pattern. It separates candidates who know fixed-size windows from those who truly understand how to grow and shrink windows based on a condition. The array, sliding window, binary search, and prefix sum interview pattern are all applicable here.

Algorithmic pattern used

The primary approach is the two-pointer sliding window. Maintain a window with left and right pointers. Expand right to increase the sum; once the sum ≥ target, record the window size and shrink from the left to try to find a smaller valid window. This gives O(n) time complexity. An alternative O(n log n) approach uses prefix sums with binary search — for each right endpoint, binary search for the leftmost left index where the subarray sum ≥ target.

Example explanation

Array: [2, 3, 1, 2, 4, 3], target = 7.

• Expand: [2]=2, [2,3]=5, [2,3,1]=6, [2,3,1,2]=8 ≥ 7. Window size 4.
• Shrink left: [3,1,2]=6 < 7. Can't shrink further.
• Expand: [3,1,2,4]=10 ≥ 7. Size 4 → shrink: [1,2,4]=7 ≥ 7. Size 3 → shrink: [2,4]=6 < 7.
• Expand: [2,4,3]=9 ≥ 7. Size 3 → shrink: [4,3]=7 ≥ 7. Size 2 ← minimum!

Common mistakes candidates make

• Using a fixed window size instead of a variable window that shrinks when the condition is met.
• Not updating the minimum length when the window becomes valid.
• Forgetting to continue shrinking while the window remains valid (not just once per valid state).
• Failing to return 0 when no valid subarray exists.

Interview preparation tip

Minimum Size Subarray Sum is a must-know problem. Internalize the two-pointer expansion-contraction template: move right to satisfy the condition, then move left as far as possible while it holds, recording the result each time. This template applies to dozens of subarray optimization problems. After solving it with the sliding window, also implement the binary search + prefix sum approach — knowing both demonstrates depth and strengthens your problem-solving toolkit.