IntermediateArrays
Minimum Size Subarray Sum
Problem
Given an array of positive integers nums and a positive integer k, return the length of the shortest contiguous subarray whose sum is greater than or equal to k. If no such subarray exists, return 0. The subarray must be contiguous — you may not skip elements.
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ nums[i] ≤ 10^4
- 1 ≤ k ≤ 10^9
Examples
in: nums = [2,3,1,2,4,3], k = 7
out: 2
The subarray [4,3] has sum 7 and is the shortest.
in: nums = [1,1,1,1], k = 11
out: 0
The whole array sums to 4 < 11, so no subarray works.
What this tests
- Recognising that positivity makes the window sum monotonic
- Variable-size sliding window with an expand/shrink loop
- Amortised complexity reasoning (each index enters and leaves once)
- Knowing an alternative (prefix sums + binary search) and when it is needed
- Handling the "no answer" sentinel correctly
Problem ClarificationPattern RecognitionOptimizationComplexity AnalysisEdge Cases
Progressive hints
Choose how much help you want. Each hint reveals a little more; the pattern is not named until hint 2.
Hint 1Direction
Hint 2Pattern
Hint 3Data structure
Hint 4Algorithm
Hint 5Pseudocode
Solution
Solve in your language
The editor, starter code and solution adapt to the language you pick — C++, JavaScript, TypeScript or Python.
Solve in
Candidate thinking
How a strong candidate reasons through this problem, step by step.
Try the problem yourself first (or run the mock interview), then compare your process against a strong candidate's.
Follow-up engine
Requirements change; so does the right algorithm.
F1
Can you give an
O(n log n) solution using a different technique?F2
What changes if the array may contain zeros?
F3
What if the array may contain negative numbers?
F4
Now find the number of subarrays with sum exactly
k.