Most Efficient Mode Function In Java

Question

I have a huge int array which I need to find the Mode of,

Ive seen a few methods that use 2 for loops (one nested) which seems unnecessary.

The only way I can think to find the mode with only one loop involves using Maps:

int[] elements = new int[]{....numbers...};
Map<Integer,Integer> map = new .....Map Type....;
for(int number : elements){
    if(map.containsKey(Integer.valueOf(number))){
        map.put(Integer.valueOf(number),map.get(Integer.valueOf(number))+1);
    }else{
        map.put(Integer.valueOf(number),1);
    }
}

Im not sure what kind of speed benefits using maps would actually give. Is there a better method?

Answer 1

If you use a hash map, the runtime complexity of your algorithm should be O(n): You visit each of the n elements once, and HashMap lookup and write is usually assumed to be O(1). So in total you get O(n * 1) which is O(n). If you use a tree map, you get O(n log n).

Compared to two nested loops (which sounds like O(n²)), the speed improvement is going from quadratic to linear, which is quite good: For 1000 elements, you perform 1000 "steps" instead of 1,000,000.

P.S. Getting better than linear is probably hard here -- can't imagine a way of calculating this without visiting each element at least once.