Codility: EquiLeader Solution

Approach

Calculate 2 prefix leaders, for the array and its reversed

The result is number of equal pairs

Implementation

1function solution(A) {
2  const getPrefixLeader = A => {
3    let maxOcc, maxEl
4
5    let prefixLeader = Array(A.length)
6    maxOcc = maxEl = -Infinity
7    A.reduce((acc, el, i) => {
8      const occ = (acc[el] || 0) + 1
9      acc[el] = occ
10      if (maxOcc < occ) {
11        maxOcc = occ
12        if (occ > Math.floor((i + 1) / 2)) {
13          maxEl = el
14        }
15      }
16      if (!(maxOcc > Math.floor((i + 1) / 2))) {
17        maxEl = -1
18      }
19
20      prefixLeader[i] = maxEl
21      return acc
22    }, {})
23
24    return prefixLeader
25  }
26
27  const prefixLeader = getPrefixLeader(A)
28  const prefixLeaderReversed = getPrefixLeader(A.reverse()).reverse()
29
30  return prefixLeader.filter(
31    (p, i) => p !== -1 && p === prefixLeaderReversed[i + 1]
32  ).length
33}