2016/04/02

Random position of maximum of array

Problem: return a (uniformly distributed) random position of the maximum value in a non-empty array of integers.

Example: If a=[1,2,3,2,3,1,3], the positions of the maximum value (3) are 2, 4, and 6. One of these three values has to be randomly returned (each value has the same probability to be chosen).

Solution: a simple solution is scanning the array, keeping a list of the positions of the currently found max. After the scan, one of these position is chosen randomly. This solution has linear time complexity, but requires auxiliary space that in the worst case could be of the same size of the array (all the elements are same).
A simple solution requiring constant auxiliary space could be obtained by scanning the array twice. The first time the maximum value m and the number of its occurrences c are found. Then, a random number p between 1 and c is chosen, and with a second scan, the position in which m is found for the p-th time is returned.

The optimal solution requires constant auxiliary space and one only scan. While scanning the array, we keep the maximum value m and the number of its occurrences c. We also keep the chosen position p for m, that will be returned after the scan.
Each time we find a value greater than the current maximum m, we update m, set c=1, and set p to the current position. If we find another value equal to m, we increase c and set p to the new position with probability equal to 1/c. At the end of the scan, each position in which m occurs will have been chosen with probability 1/c, where c is the final count of occurrences of m.
This can be simply proven by induction. For c=1 and c=2, it is obvious. So, assume that p was uniformly chosen among the first c-1 occurrence of m, that is, p was correctly chosen with probability 1/(c-1). We choose the new position, that is the c-th position in which m has been found, with probability 1/c, then, the probability of choosing again the old position p is 1-1/(c-1)=(c-1)/c. Globally, the probability of choosing the old position is (1/(c-1)) * ((c-1)/c) = 1/c, which is the same of that used to choose the new position.

The implementation of this algorithm is quite simple, and it is given in the following.

public int randomMaxPosition(int[] a) {
    int m=a[0];
    int c=1;
    int p=0;
    for (int i=1; i < a.length; i++) {
        if (a[i] > m) {
            m=a[i];
            c=1;
            p=i;
        } else if (a[i]==m) {
            c++;
            if (Math.random() < 1.0/c) {
                p=i;
            }
        }
    }
    return p;
}

No comments:

Post a Comment