Codility: Flags Solution

Approach

(Flag is on the peak only)

Maximum number of peaks is upper bound of sqrt(N) (N is the length of A)

Get an array of peaks to determine whether an index is peak

Decrease from max peaks, for each iteration, check if that the number of peak is valid

The number of peak is whether valid or not is based on the condition: distance between any 2 flag should be >= number of flags

Implementation

1function solution(A) {
2  const N = A.length
3  const isPeak = (a, b, c) => a < b && b > c
4  const checkFlagsValid = (flags, peaks) => {
5    const N = peaks.length
6    let flagsLeft = flags
7    let i = 1
8    while (i < N - 1 && flagsLeft) {
9      if (peaks[i]) {
10        flagsLeft -= 1
11        i += flags
12      } else {
13        i += 1
14      }
15    }
16    return flagsLeft === 0
17  }
18
19  const peaks = Array(N).fill(false)
20  let peaksCount = 0
21  for (let i = 1; i < N - 1; i++) {
22    if (isPeak(A[i - 1], A[i], A[i + 1])) {
23      peaksCount++
24      peaks[i] = true
25    }
26  }
27
28  let maxFlags = Math.min(Math.ceil(Math.sqrt(N)), peaksCount)
29  while (maxFlags) {
30    if (checkFlagsValid(maxFlags, peaks)) {
31      break
32    }
33    maxFlags--
34  }
35  return maxFlags
36}

References

https://codility.com/media/train/solution-flags.pdf