Flags 100% Solution in Javascript
Question
Solution
function solution(A) { let peaks = new Array(A.length).fill(false); let peakCount = 0; for (let i = 1; i < A.length-1; i++) { if (A[i-1] < A[i] && A[i] > A[i+1]) { peaks[i] = true; peakCount++; } } if (peakCount === 0 || peakCount === 1) return peakCount; let left = 2; let right = peakCount; let result; while (left <= right) { let middle = Math.floor((left+right)/2); let success = CheckFlags(peaks, middle); if (success) { result = middle; left = middle + 1; } else { right = middle - 1; } } return result; } function CheckFlags(peaks, flags) { let minGap = flags; let pos = 0; while (pos < peaks.length && flags > 0) { if (peaks[pos]) { flags--; pos += minGap; } else { pos++; } } return flags === 0; }
Note
Binary Search! or you will get 66% result because of time out
while (left <= right) { let middle = Math.Floor((left + right)/2); let success = checkFlags(); if (success) { result = middle; left = middle + 1; } else { right = middle -1; } } return middle;
StackOverFlow of my 80% solution
Official Answer https://codility.com/media/train/solution-flags.pdf