Pattern this teaches:Sliding Window
Minimum Size Subarray Sum
A medium Sliding Window interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Sliding Window
- Sheets
- 2
- Core for
- 6 roles
The problem
Given an array of positive integers and a target sum, find the minimal length of a contiguous subarray whose sum is at least the target.
Example 1
- Input
- target = 9, nums = [3,1,4,2,5,2]
- Output
- 3
- Why
- No two neighbours reach 9, but the three values 2, 5, 2 add up to exactly 9.
Example 2
- Input
- target = 6, nums = [2,6,3]
- Output
- 1
- Why
- The single element 6 already reaches the target.
Constraints
- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
How to think about it
Updated 2026-09-29Every element is strictly positive, so extending the right endpoint can only increase the sum and advancing the left endpoint can only decrease it. Once a running span meets the target threshold, stretching it further to the right cannot yield a shorter valid window, meaning the left boundary must immediately contract to seek smaller lengths.
Approaches, worst first
Check all pairs
time O(n^2) · space O(1)
Evaluate the sum of every possible subarray from each starting index. Redundant because expanding an already qualified span wastes time exploring longer candidates.
Prefix sums with binary search
time O(n log n) · space O(n)
Build an array of cumulative sums. For each starting point, binary search for the first end index that reaches prefix[i] + target. Monotonicity holds because terms are positive, but the search takes extra time.
Shrinkable sliding windowWrite this one
time O(n) · space O(1)
Expand the right pointer while accumulating values into a running total. Whenever the sum reaches the target, record the current length and shrink from the left until the sum drops back below target.
Where people lose marks · 3
- Returning n + 1 or the sentinel initial value when no subarray ever reaches target instead of returning 0.
- Using an if statement instead of a while loop when shrinking the left edge skips further contractions that still satisfy the target.
- This two-pointer contraction relies strictly on all elements being positive; if zero or negative values were allowed, shrinking could increase or preserve the sum.
The theory behind it
Sliding Window — the ground this problem stands on. All Sliding Window problems
What Sliding Window is
A sliding window is an adjustable magnifying lens placed over a continuous segment of a sequence. Rather than recalculating metrics for every potential subsection from scratch, the window expands rightward by absorbing fresh elements and contracts leftward to expel stale entries. Only data currently framed within the window borders contributes to the active calculation.
When to reach for it
Reach for a sliding window when a question asks for the longest, shortest, or optimal contiguous subarray or substring matching a constraint. Key signals include fixed window sizes like maximum sum across k consecutive values, or dynamic criteria like finding the shortest substring holding all target characters. If the target subset must form an unbroken continuous run, window mechanics replace repetitive segment rescanning.
How the pattern works
Maintain two boundary indices, left and right, defining the active interval alongside a running state accumulator. In each step, expand the right boundary to incorporate the incoming element into state totals. When current state violates the designated problem constraints, increment the left boundary while deducting departing values until validity is restored. Update your tracking metric, whether minimum window length or maximum score, only during valid intervals.
More Sliding Window problems
Target Roles
Core requirement for 6 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .