-
Notifications
You must be signed in to change notification settings - Fork 10
/
Copy pathminAvgTwoSlice.js
39 lines (31 loc) · 1.07 KB
/
minAvgTwoSlice.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function solution(A) {
/* Consider a slice of size 4. You can always break it down into two slices of size 2.
One of two cases may happen. First, the averages of the two slices are the same, in which case,
you could just use the first average. Second, the averages are different, in which case,
your original slice cannot be the min-average slice.So the slice of size 4 is either duplicated
with a shorter slice, or not the min. You cannot make this argument with a slice of size 3. */
const N = A.length;
let lowestIndex = 0;
let lowestAvg = Number.MAX_SAFE_INTEGER;
let last = undefined;
let lastButOne = undefined;
for (let i = 0; i < N; i++) {
if (last !== undefined) {
const avg = (last + A[i]) / 2;
if (avg < lowestAvg) {
lowestAvg = avg;
lowestIndex = i - 1;
}
}
if (lastButOne !== undefined) {
const avg = (lastButOne + last + A[i]) / 3;
if (avg < lowestAvg) {
lowestAvg = avg;
lowestIndex = i - 2;
}
}
lastButOne = last;
last = A[i];
}
return lowestIndex;
}