Codility Equi-Leader

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:

static int equiLeader(int[] a){
  int len = a.length;
  int equi_leaders = 0;

  // first, compute the leader
  int leader = a[0];
  int ctr = 1;

  for(int i = 1; i < a.length; i++){
    if(a[i] == leader) ctr++;
    else ctr--;
    if(ctr == 0){
      ctr = 1;
      leader = a[i];
    }
  }

  // check if it's a leader?
  int total = 0;
  for(int i : a){
    if(i == leader) total++; 
  }

  if(total <= (len/2)) return 0; // impossible

  int ldrCount = 0;
  for(int i = 0; i < a.length; i++){
    if(a[i] == leader) ldrCount++;
    int leadersInRightPart = (total - ldrCount);
    if(ldrCount > (i+1)/2   &&   leadersInRightPart > (len-i-1)/2){
      equi_leaders++;
    }
  }

  return equi_leaders;
}