This post is about the Codility Equi-leader challenge. The description is copyrighted, so have a look at the link on the problem description.

The key idea that wasn’t allowing me to come up with a good solution is the following: If you have an array \(A\) which has leader \(x\) (the leader is the unique element that occurs more than in half of the array), then for every separation of \(A\) into \(A[0..i), A[i..n)\), if they have the same leader, then the leader of both is \(x\). This follows from noticing that if \(z\) is a leader in \(A[0..i)\), then it occurs more than \(\lceil \frac{i}{2} \rceil\) elements, and similarly, if z is the leader of \(A[i..n)\), then x occurs more than \(\lceil \frac{n-i}{2} \rceil\). In total, if both slices have leader \(z\), it must occur more than \(\lceil \frac{n}{2} \rceil\), which means that \(y=x\) as required.

The Java implementation that scores 100/100: