find if there are more than n/2 items that match in a list of n items. O(nlog(n))

Question

how to find if any item in a list of n items is duplicated more then n/2 times. I want it to be quick, so it should be O(nlogn) and here's the kicker: you can only check if items are equal, nothing else. i'm have a hard time doing better than O(n^2)

Answer 1

If you can only check for equality then here is an O(nlogn) solution:

• Sort the list in O(nlogn) time
• Let the middle element be m in the sorted array
• Now if there is an element which is repeated more than n/2 times it can only be m. so now you can check the frequency of m by iterating to the right of middle index and to the left of middle index. If it is more than n/2 you found your answer, otherwise the element doesn't exists.

If you are allowed to do more than checking for equality you can just go through the array and store the frequency of elements in a HashMap and then check if the frequency is more than n/2. This solution is O(n) in time complexity.

Code for O(n) solution with HashMap:

public int getDuplicated(List<Integer> a) {
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    int n = a.size();
    for (int i = 0; i < a.size(); i++) {
        if (map.containsKey(a.get(i))) {
            // increasing the frequency
            map.put(a.get(i), map.get(a.get(i)) + 1);
        } else {
            map.put(a.get(i), 1);
        }
        if (map.get(a.get(i)) > n / 2) {
            // element found
            return a.get(i);
        }
    }
    // returning -1 if could not find the element
    return -1;
}