// return mode of non-empty array $a$ of non-negative numbers
// (for efficiency, assume the elements of $a$ are *dense*,
// i.e. do not have huge gaps, since otherwise, $tally$ is *huge*)

public class array_mode {
    public static void main(String[] args) {
	int[] X = {1,2,2,3,3,3,5}; // 3 is the mode of $a$
	
	System.out.println("Mode: " + mode(X) );
    }
    
    public static int mode(int[] a) {
	// set max to largest element of $a$
           int max = a[0]; // max element of $a$
	   for (int i = 1; i<a.length; i++) max = Math.max(max, a[i]);
	// count frequencies of elements in $a$
	   int[] tally = new int[max+1]; // tally[i] == frequency of i
	   for (int k = 0; k<a.length; k++) tally[a[k]]++;
        // search: find mode/position j of max frequency
	   int j = 0; // mode so far
	   for (int i = 1; i<tally.length; i++) 
	       if (tally[i]>tally[j]) 
		   j = i;
        return j;
	
    }
    
}