Peaks 100% Solution in Javascript
Question
Solution
function solution(A) { let prefixSumPeaks = new Array(A.length+1).fill(0); let peakArray = new Array(A.length).fill(0); let peakCount = 0; for (let i = 1; i < A.length-1; i++) { if (A[i-1] < A[i] && A[i] > A[i+1]) { peakArray[i] = 1; peakCount++; } } if (peakCount === 0 || peakCount === 1) return peakCount; for (let i = 1; i < prefixSumPeaks.length; i++) { prefixSumPeaks[i] = prefixSumPeaks[i-1] + peakArray[i-1]; } let blocks; for (blocks = peakCount; blocks >= 1; blocks--) { if (A.length % blocks !== 0) continue; let blockSize = A.length / blocks; let lackOfPeak = false; for (let i = 1; i <= blocks; i++) { if (prefixSumPeaks[blockSize*i] - prefixSumPeaks[blockSize*(i-1)] === 0) { lackOfPeak = true; break; } } if (!lackOfPeak) break; } return blocks; }
Note
Beware of the prefix sum calculation and all the upper bound of for-loop.
https://codility.com/media/train/3-PrefixSums.pdf
Why the complexity is O(n log(log(n)))?