Equileader solution

Equileader solution

  June 27, 2018    

---

Algorithm:

First find majority element.
Now we have a index i such that i lies between 0 to n 

Left count will hold count of majority element till i and from i+1 to n we can get by totalcount-leftcount.
Now just check if both the counts are greater than window size /2

Code:


class dmg{ public int solution(int[] a) { int n=a.length; int count=1; int ele=a[0]; for(int i=1;i<n;++i) { if(a[i]==ele) ++count; else --count; if(count==0) { count=1; ele=a[i]; } } count=0; for(int i=0;i<n;++i) { if(a[i]==ele) ++count; } if(count<n/2) return 0; int lcount=0,res=0; for(int i=0;i<n;++i) { if(a[i]==ele) ++lcount; if(lcount>(i+1)/2 && (count-lcount)>(n-i-1)/2) ++res; } return res; } }