Permalink
Aug 28, 2021
Newer
100644
55 lines (40 sloc)
1.49 KB
1
/**
2
3
Given an array of positive numbers and a positive number ‘S’,
4
find the length of the smallest contiguous subarray whose sum is greater than or equal to ‘S’.
5
Return 0, if no such subarray exists.
6
7
8
Example 1:
9
Input: [2, 1, 5, 2, 3, 2], S=7
10
Output: 2
11
Explanation: The smallest subarray with a sum great than or equal to '7' is [5, 2].
12
13
Example 2:
14
Input: [2, 1, 5, 2, 8], S=7
15
Output: 1
16
Explanation: The smallest subarray with a sum greater than or equal to '7' is [8].
17
18
Example 3:
19
Input: [3, 4, 1, 1, 6], S=8
20
Output: 3
21
Explanation: Smallest subarrays with a sum greater than or equal to '8' are [3, 4, 1] or [1, 1, 6].
22
23
*/
24
25
26
function smallestSubArrayWithGivenSum(inputArr, target) {
27
var start = 0
28
var smallestLength = Infinity
29
var sum = 0
30
31
for (end = 0; end < inputArr.length; end++){
32
sum += inputArr[end]
33
34
while (sum >= target) {
35
smallestLength = Math.min(smallestLength, end - start + 1)
36
sum -= inputArr[start]
37
start += 1
38
}
39
}
40
41
if(smallestLength === Infinity){
42
return 0
43
}
44
45
return smallestLength
46
}
47
48
49
let input = [2, 1, 5, 2, 3, 2], S=7
50
let input1 = [2, 1, 5, 2, 8], S1=7
51
let input2 = [3, 4, 1, 1, 6], S2=8
52
53
console.log("The smallest subarray with given sum", smallestSubArrayWithGivenSum(input, S))
54
console.log("The smallest subarray with given sum", smallestSubArrayWithGivenSum(input1, S1))
55
console.log("The smallest subarray with given sum", smallestSubArrayWithGivenSum(input2, S2))