Smallest subarray with sum greater than a given value

Medium

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}