Find an index of an array such that its value occurs at more than half of indices in the array.
- Difficulty Level: Easy
- Question URL: https://app.codility.com/programmers/lessons/8-leader/dominator/
- Time Complexity:
Solution:
Solution to Codility's Dominator 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 an index of an array such that its value occurs at more than half of indices in the array. You can find the question of this Dominator problem in the Codility website.
package Codility.Lesson8;
import java.util.*;
public class Dominator {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] in2 = { 3, 4, 3, 2, 3, -1, 3, 3 };
int result = solution(in2);
System.out.println(result);
}
public static int solution(int[] A) {
// write your code in Java SE 8
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
int dominatorKey = -1;
int dominatorValue = -1;
for (int i = 0; i < A.length; i++) {
if (hm.containsKey(A[i])) {
hm.put(A[i], hm.get(A[i]) + 1);
} else {
hm.put(A[i], 1);
}
}
if (hm.size() == 0)
return -1;
if (hm.size() == 1)
return 0;
for (Map.Entry<Integer, Integer> entry : hm.entrySet()) {
if (entry.getValue() > dominatorValue) {
dominatorKey = entry.getKey();
dominatorValue = entry.getValue();
}
}
if (dominatorValue > (A.length / 2)) {
for (int i = 0; i < A.length; i++) {
if (A[i] == dominatorKey) {
return i;
}
}
}
return -1;
}
}