Find the index S such that the leaders of the sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N - 1] are the same.
- Difficulty Level: Easy
- Question URL: https://app.codility.com/programmers/lessons/8-leader/equi_leader/
- Time Complexity: O(N)
Solution:
Solution to Codility's EquiLeader problem which is from the Codility Lesson 8: Leader and, is solved in Java 8 with 100% performance and correctness scores. The goal here is to find the index s such that the leaders of the sequences a[0], a[1], ..., a[s] and a[s + 1], a[s + 2], ..., a[n - 1] are the same. You can find the question of this EquiLeader problem in the Codility website.
package Codility.Lesson8;
import java.util.*;
public class EquiLeader {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] int1 = { 4, 3, 4, 4, 4, 2};
int result1 = solution(int1);
System.out.println(result1);
}
public static int solution(int[] A) {
// write your code in Java SE 8
if(A.length==1) {
return 0;
}
int value = A[0];
int size=0;
for(int i=0;i<A.length;i++) {
if(size==0) {
size++;
value = A[i];
}else {
if(A[i]==value) {
size++;
}else {
size--;
}
}
}
//System.out.println("Value: "+ value);
int candidate = -1;
int count = 0;
if(size>0) {
candidate = value;
}
for(int i=0;i<A.length;i++) {
if(A[i]==candidate) {
count++;
}
}
if(count<=A.length/2) {
return 0;
}
int leader = candidate;
int equiCount = 0;
int leaderCount = 0;
for(int i=0;i<A.length;i++) {
if (A[i] == leader) {
leaderCount++;
}
if(leaderCount>(i+1)/2 && (count-leaderCount)>(A.length-i-1)/2) {
equiCount++;
}
}
return equiCount;
}
}