Tasks Details
easy
1.
EquiLeader
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.
Task Score
100%
Correctness
100%
Performance
100%
A non-empty array A consisting of N integers is given.
The leader of this array is the value that occurs in more than half of the elements of A.
An equi leader is an index S such that 0 ≤ S < N − 1 and two sequences A[0], A[1], ..., A[S] and A[S + 1], A[S + 2], ..., A[N − 1] have leaders of the same value.
For example, given array A such that:
A[0] = 4 A[1] = 3 A[2] = 4 A[3] = 4 A[4] = 4 A[5] = 2we can find two equi leaders:
- 0, because sequences: (4) and (3, 4, 4, 4, 2) have the same leader, whose value is 4.
- 2, because sequences: (4, 3, 4) and (4, 4, 2) have the same leader, whose value is 4.
The goal is to count the number of equi leaders.
Write a function:
class Solution { public int solution(int[] A); }
that, given a non-empty array A consisting of N integers, returns the number of equi leaders.
For example, given:
A[0] = 4 A[1] = 3 A[2] = 4 A[3] = 4 A[4] = 4 A[5] = 2the function should return 2, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 8
Time spent on task 89 minutes
Notes
not defined yet
Code: 13:29:24 UTC,
java,
autosave
Code: 13:29:28 UTC,
java,
verify,
result: Passed
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> firstCountMap = new HashMap<>();
Map<Integer, Integer> secondCountMap = new HashMap<>();
int firstLeader = A[0];
int secondLeader = A[0];
int count = 0;
for (int a : A) {
secondCountMap.put(a, secondCountMap.getOrDefault(a, 0) + 1);
if (secondCountMap.get(secondLeader) < secondCountMap.get(a)) {
secondLeader = a;
}
}
if (secondCountMap.get(secondLeader) <= A.length / 2) {
return count;
}
for (int i=0; i<A.length-1; i++) {
firstCountMap.put(A[i], firstCountMap.getOrDefault(A[i], 0) + 1);
secondCountMap.put(A[i], secondCountMap.get(A[i]) - 1);
if (firstCountMap.get(firstLeader) < firstCountMap.get(A[i])) {
firstLeader = A[i];
}
if (secondCountMap.get(secondLeader) < secondCountMap.get(A[i])) {
secondLeader = A[i];
}
if (firstCountMap.get(firstLeader) > (i + 1) / 2.0 && secondCountMap.get(secondLeader) > (A.length - i - 1) / 2.0 && firstLeader == secondLeader) {
count++;
}
}
return count;
}
}
Analysis
Code: 13:49:00 UTC,
java,
verify,
result: Passed
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> firstCountMap = new HashMap<>();
Map<Integer, Integer> secondCountMap = new HashMap<>();
int firstLeader = A[0];
int secondLeader = A[0];
int count = 0;
for (int a : A) {
secondCountMap.put(a, secondCountMap.getOrDefault(a, 0) + 1);
if (secondCountMap.get(secondLeader) < secondCountMap.get(a)) {
secondLeader = a;
}
}
if (secondCountMap.get(secondLeader) <= A.length / 2) {
return count;
}
for (int i=0; i<A.length-1; i++) {
firstCountMap.put(A[i], firstCountMap.getOrDefault(A[i], 0) + 1);
secondCountMap.put(A[i], secondCountMap.get(A[i]) - 1);
if (firstCountMap.get(firstLeader) < firstCountMap.get(A[i])) {
firstLeader = A[i];
}
if (secondCountMap.get(secondLeader) < secondCountMap.get(A[i])) {
secondLeader = A[i];
}
if (firstCountMap.get(firstLeader) > (i + 1) / 2.0 && secondCountMap.get(secondLeader) > (A.length - i - 1) / 2.0 && firstLeader == secondLeader) {
count++;
}
}
return count;
}
}
Analysis
Code: 14:14:07 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> firstCountMap = new HashMap<>();
Map<Integer, Integer> secondCountMap = new HashMap<>();
int firstLeader = A[0];
int secondLeader = A[0];
int count = 0;
for (int a : A) {
secondCountMap.put(a, secondCountMap.getOrDefault(a, 0) + 1);
if (secondCountMap.get(secondLeader) < secondCountMap.get(a)) {
secondLeader = a;
}
}
if (secondCountMap.get(secondLeader) <= A.length / 2) {
return count;
}
for (int i=0; i<A.length-1; i++) {
firstCountMap.put(A[i], firstCountMap.getOrDefault(A[i], 0) + 1);
secondCountMap.put(A[i], secondCountMap.get(A[i]) - 1);
if (firstCountMap.get(firstLeader) < firstCountMap.get(A[i])) {
firstLeader = A[i];
}
if (secondCountMap.get(secondLeader) < secondCountMap.get(A[i])) {
secondLeader = A[i];
}
if (firstCountMap.get(firstLeader) > (i + 1) / 2.0 && secondCountMap.get(secondLeader) > (A.length - i - 1) / 2.0 && firstLeader == secondLeader) {
count++;
}
}
return count;
}
}
Code: 14:26:54 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> firstCountMap = new HashMap<>();
Map<Integer, Integer> secondCountMap = new HashMap<>();
int firstLeader = A[0];
int secondLeader = A[0];
int count = 0;
for (int a : A) {
secondCountMap.put(a, secondCountMap.getOrDefault(a, 0) + 1);
if (secondCountMap.get(secondLeader) < secondCountMap.get(a)) {
secondLeader = a;
}
}
if (secondCountMap.get(secondLeader) <= A.length / 2) {
return count;
}
for (int i=0; i<A.length-1; i++) {
}
return count;
}
}
Code: 14:28:41 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
Map<Integer, Integer> firstCountMap = new HashMap<>();
Map<Integer, Integer> secondCountMap = new HashMap<>();
int firstLeader = A[0];
int secondLeader = A[0];
int count = 0;
for (int a : A) {
}
if (secondCountMap.get(secondLeader) <= A.length / 2) {
return count;
}
for (int i=0; i<A.length-1; i++) {
}
return count;
}
}
Code: 14:28:51 UTC,
java,
autosave
Code: 14:48:56 UTC,
java,
autosave
Code: 14:49:11 UTC,
java,
autosave
Code: 14:49:41 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} el
}
if (secondCountMap.get(secondLeader) <= A.length / 2) {
return count;
}
for (int i=0; i<A.length-1; i++) {
}
return count;
}
}
Code: 14:50:01 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size;
int value =
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
if (secondCountMap.get(secondLeader) <= A.length / 2) {
return count;
}
for (int i=0; i<A.length-1; i++) {
}
return count;
}
}
Code: 14:50:22 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value =
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
if (secondCountMap.get(secondLeader) <= A.length / 2) {
return count;
}
for (int i=0; i<A.length-1; i++) {
}
return count;
}
}
Code: 14:51:39 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value =
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
i
for (int i=0; i<A.length-1; i++) {
}
return count;
}
}
Code: 14:51:49 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value =
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
if (size > 0) {
}
for (int i=0; i<A.length-1; i++) {
}
return count;
}
}
Code: 14:52:19 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value =
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
int leaderCount = 0;
if (size > 0) {
if
}
for (int i=0; i<A.length-1; i++) {
}
return count;
}
}
Code: 14:52:33 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value =
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
int leaderCount = 0;
if (size > 0) {
for (int a : A) {
if ()
leaderCount++;
}
}
for (int i=0; i<A.length-1; i++) {
}
return count;
}
}
Code: 14:52:44 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value =
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
int leaderCount = 0;
if (size > 0) {
for (int a : A) {
if (value == a)
leaderCount++;
}
}
for (int i=0; i<A.length-1; i++) {
}
return count;
}
}
Code: 14:53:15 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value =
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
int leaderCount = 0;
if (size == 0) {
return 0;
} else {
for (int a : A) {
if (value == a)
leaderCount++;
}
}
for (int i=0; i<A.length-1; i++) {
}
return count;
}
}
Code: 14:53:26 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value =
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
int leaderCount = 0;
if (size == 0) {
return 0;
} else {
for (int a : A) {
if (value == a) {
leaderCount++;
}
}
}
for (int i=0; i<A.length-1; i++) {
}
return count;
}
}
Code: 14:53:40 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value = 0;
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
int leaderCount = 0;
if (size == 0) {
return 0;
} else {
for (int a : A) {
if (value == a) {
leaderCount++;
}
}
}
for (int i=0; i<A.length-1; i++) {
}
return count;
}
}
Code: 14:54:11 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value = 0;
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
int leaderCount = 0;
if (size == 0) {
return 0;
} else {
for (int a : A) {
if (value == a) {
leaderCount++;
}
}
}
for (int a ) {
}
for (int i=0; i<A.length-1; i++) {
}
return count;
}
}
Code: 14:54:29 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value = 0;
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
int leaderCount = 0;
if (size == 0) {
return 0;
} else {
for (int a : A) {
if (value == a) {
leaderCount++;
}
}
}
for (int a : A) {
if () {
}
}
return count;
}
}
Code: 14:54:39 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value = 0;
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
int leaderCount = 0;
if (size == 0) {
return 0;
} else {
for (int a : A) {
if (value == a) {
leaderCount++;
}
}
}
for (int a : A) {
if (a == )
if () {
}
}
return count;
}
}
Code: 14:54:58 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value = 0;
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
int leaderCount = 0;
if (size == 0) {
return 0;
} else {
for (int a : A) {
if (value == a) {
leaderCount++;
}
}
}
for (int a : A) {
if (a == )
if () {
}
}
return count;
}
}
Code: 14:55:10 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value = 0;
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
int leaderCount = 0;
if (size == 0) {
return 0;
} else {
for (int a : A) {
if (value == a) {
leaderCount++;
}
}
}
for (int a : A) {
if (value == a) {
}
if () {
}
}
return count;
}
}
Code: 14:55:38 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value = 0;
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
int leaderCount = 0;
if (size == 0) {
return 0;
} else {
for (int a : A) {
if (value == a) {
leaderCount++;
}
}
}
int firstLeaderCount = 0;
for (int a : A) {
if (value == a) {
firstLeaderCount++;
}
if (leaderCount - ) {
count++;
}
}
return count;
}
}
Code: 14:55:49 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value = 0;
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
int leaderCount = 0;
if (size == 0) {
return 0;
} else {
for (int a : A) {
if (value == a) {
leaderCount++;
}
}
}
int firstLeaderCount = 0;
for (int a : A) {
if (value == a) {
firstLeaderCount++;
}
if (leaderCount) {
count++;
}
}
return count;
}
}
Code: 14:56:04 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value = 0;
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
int leaderCount = 0;
if (size == 0) {
return 0;
} else {
for (int a : A) {
if (value == a) {
leaderCount++;
}
}
}
int firstLeaderCount = 0;
for (int a : A) {
if (value == a) {
firstLeaderCount++;
}
if (firstLeaderCount > ) {
count++;
}
}
return count;
}
}
Code: 14:56:35 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value = 0;
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
int leaderCount = 0;
if (size == 0) {
return 0;
} else {
for (int a : A) {
if (value == a) {
leaderCount++;
}
}
}
int firstLeaderCount = 0;
for (int i=0; i<A.length; i++) {
if (value == a) {
firstLeaderCount++;
}
if (firstLeaderCount > (i + 1) / 2.0 ) {
count++;
}
}
return count;
}
}
Code: 14:57:06 UTC,
java,
autosave
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value = 0;
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
int leaderCount = 0;
if (size == 0) {
return 0;
} else {
for (int a : A) {
if (value == a) {
leaderCount++;
}
}
}
int firstLeaderCount = 0;
for (int i=0; i<A.length; i++) {
if (value == a) {
firstLeaderCount++;
}
if (firstLeaderCount > (i + 1) / 2.0 && leaderCount - firstLeaderCount > A.length - i - 1 / 2.0 ) {
count++;
}
}
return count;
}
}
Code: 14:57:12 UTC,
java,
verify,
result: Failed
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value = 0;
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
int leaderCount = 0;
if (size == 0) {
return 0;
} else {
for (int a : A) {
if (value == a) {
leaderCount++;
}
}
}
int firstLeaderCount = 0;
for (int i=0; i<A.length; i++) {
if (value == a) {
firstLeaderCount++;
}
if (firstLeaderCount > (i + 1) / 2.0 && leaderCount - firstLeaderCount > (A.length - i - 1) / 2.0 ) {
count++;
}
}
return count;
}
}
Analysis
Compile error
Solution.java:32: error: cannot find symbol if (value == a) { ^ symbol: variable a location: class Solution 1 error
Code: 14:57:20 UTC,
java,
verify,
result: Passed
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value = 0;
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
int leaderCount = 0;
if (size == 0) {
return 0;
} else {
for (int a : A) {
if (value == a) {
leaderCount++;
}
}
}
int firstLeaderCount = 0;
for (int i=0; i<A.length; i++) {
if (value == A[i]) {
firstLeaderCount++;
}
if (firstLeaderCount > (i + 1) / 2.0 && leaderCount - firstLeaderCount > (A.length - i - 1) / 2.0) {
count++;
}
}
return count;
}
}
Analysis
Code: 14:57:28 UTC,
java,
verify,
result: Passed
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value = 0;
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
int leaderCount = 0;
if (size == 0) {
return 0;
} else {
for (int a : A) {
if (value == a) {
leaderCount++;
}
}
}
int firstLeaderCount = 0;
for (int i=0; i<A.length; i++) {
if (value == A[i]) {
firstLeaderCount++;
}
if (firstLeaderCount > (i + 1) / 2.0 && leaderCount - firstLeaderCount > (A.length - i - 1) / 2.0) {
count++;
}
}
return count;
}
}
Analysis
Code: 14:57:33 UTC,
java,
final,
score: 
100
import java.util.*;
class Solution {
public int solution(int[] A) {
int count = 0;
int size = 0;
int value = 0;
for (int a : A) {
if (size == 0) {
value = a;
size++;
} else if (value == a) {
size++;
} else {
size--;
}
}
int leaderCount = 0;
if (size == 0) {
return 0;
} else {
for (int a : A) {
if (value == a) {
leaderCount++;
}
}
}
int firstLeaderCount = 0;
for (int i=0; i<A.length; i++) {
if (value == A[i]) {
firstLeaderCount++;
}
if (firstLeaderCount > (i + 1) / 2.0 && leaderCount - firstLeaderCount > (A.length - i - 1) / 2.0) {
count++;
}
}
return count;
}
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
1.
0.004 s
OK
2.
0.004 s
OK
1.
0.004 s
OK
1.
0.008 s
OK