Smallest subarray with sum greater than a given value
Problem
Given an array of positive integers and a value x, return the length of the smallest contiguous subarray whose sum is strictly greater than x, or 0 if none exists.
Example 1
Input: arr = [1, 4, 45, 6, 0, 19], x = 51 Output: 3
[4, 45, 6] sums to 55.
Also asked as: Smallest Subarray with sum greater than a given value
Test cases
Case 1
Input: [1,4,45,6,0,19], 51 Expected: 3
Case 2
Input: [1,10,5,2,7], 9 Expected: 1
Case 3
Input: [1,2,4], 8 Expected: 0
View solutionHide solution1 approach
1. Sliding window (positive numbers)
Time O(n)Space O(1)
Grow the window on the right; whenever the sum exceeds x, shrink from the left while it still does, recording the length.
function smallestSubWithSum(a, x) { let sum = 0, start = 0, best = Infinity; for (let end = 0; end < a.length; end++) { sum += a[end]; while (sum > x) { best = Math.min(best, end - start + 1); sum -= a[start++]; } } return best === Infinity ? 0 : best;}