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;
}

Array rotation

Problem: left-rotate an array of k positions in place, in linear time and constant auxiliary space.

Solution: If k=1, then we can save the first element in a temporary variable, write in each position, except the last one, the value in the subsequent position, and, finally, write the temporary variable in the last position.

If k>1, we can use the same approach several times for different subsets (not subarrays!) of the array.
Assume that n is the length of the array and k<n (otherwise, we can set k=k%n).
We can save the first element in a temporary variable.
Then, starting from position p=0, we can write in that position the value in position (p+k)%n. Then set p=(p+k)%n and repeat until (p+k)%n is equal to 0.
When  (p+k)%n is 0, in p we write the temporary variable, because in 0 we previously wrote the value in position p+k.
If k and n are co-prime, this approach enables to scan all the array (i.e., (p+k)%n becomes equal to 0 after n-1 iterations). In fact, being p=(l-1)*k, we have that (l*k)%n is 0 only if l is a multiple of n, when gcd(k,n)=1. Thus, p=0 when l=0 (at the beginning) and then when l becomes equal to n (i.e., after a complete scan).
Instead, if n and k are not co-prime, being nc=gcd(n,k)>1, after n/nc-1 iterations (p+k)%n will become 0. Therefore, not all the elements can be rotated in this way, but only n/nc.
However, if set p=1, and we iterate again until (p+k)%n is equal to 1, we can rotate other n/nc elements.
We can repeat this process nc times, setting the initial value of p to 0,1,...,nc-1, thus completing the rotation of all the elements of the array.

A Java implementation is given in the following.

  
public int gcd(int a, int b) {
    if (b==0) {
        return a;
    }
    return gcd(b, a%b);
}

public <T> void rotateArray(T[] a, int k) {
    k = k % a.length;
    int numberOfCycles=gcd(a.length, k);
    int lengthOfCycles=a.length/numberOfCycles;
    for (int i = 0; i < numberOfCycles; i++) {            
        T temp = a[i];
        int p = i;
        for (int j = 0; j < lengthOfCycles-1; j++) {
            a[p%a.length] = a[(p + k)%a.length];
            p+=k;
        }
        a[p%a.length] = temp;
    }
}

Another nice solution is obtained by first inverting the subarray consisting of the first k elements, then then subarray consisting of the last n-k elements, and finally inverting the whole array.
Each element with index i<k after the first inversion will be in position k-i-1, and after the third inversion in position n-1-k+i+1=n-k+i. Each element with index i≥k after the second inversion will be in position n-1-i+k, and after the third inversion in position n-1-n+1+i-k=i-k. The implementation of this algorithm is much simpler than the previous one.

public <T> void invertSubarray(T[] a, int lo, int hi) {
    while (lo < hi) {
        T temp = a[lo];
        a[lo] = a[hi];
        a[hi] = temp;
        lo++;
        hi--;
    }
}

public <T> void rotateArray(T[] a, int k) {
    k = k % a.length;
    invertSubarray(a, 0, k-1);
    invertSubarray(a, k, a.length-1);
    invertSubarray(a, 0, a.length-1);
}

Median of two sorted arrays

Problem: Let a and b be two sorted arrays. Find the median of the array that would be obtained by merging a and b.

Note: The median of a sorted array with an even number of elements is the average of the two elements in the middle of the array. E.g., the median of (1,2,3,4) is (2+3)/2=2.5

Solution: A naive solution would be processing a and b using the same technique of the merge routine of the merge-sort algorithm. We do not need to materialize the merged array, we can just save the element/s that would be in the middle. This approach requires O(|a|+|b|) time and constant auxiliary space.

Indeed, the problem can be solved in time O(log(|a|)+log(|b|)) and constant auxiliary space.

Let's think to a simple case that can be solved in constant time. Assume that the size of one of the arrays, say a, as length not greater then 2 (|a| ≤ 2). By means of some examples, it is easy to see that we can focus our attention the three (|b| is odd) or four (|b| is even) elements in the middle of b, or all the elements of b, if |b|<3.
In this case, the naive approach can be applied, and since it will work on at most 6 elements, whatever |a|+|b| is, its complexity can be considered constant.
Summarizing, we are able to solve the problem in constant time and space when one array has at most two elements, whatever the size of the other array is.

Now, lets try to efficiently reduce the general problem to the above situation, i.e., one of the two arrays has size not larger than two. Let m_a and m_b be the median of a and b, respectively. We can observe that if m=m_a=m_b, then m is also the value of the median of merged array.
But assume that we are not so lucky, and m_a<m_b (the case m_a>m_b can be handled symmetrically).
Let h be the minimum between the number of elements on the left of m_a and the number of elements on the right of m_b. The global median cannot be either in the first h elements of a or in the last h elements of b.
An informal intuition is the following. Being a_h the h-th element of a, the number of elements less than a_h in a plus the number of elements less than a_h in b is less than one half of |a|+|b|. Similarly, being b^h the h-th last element of b, the number of elements greater than b^h in b plus the number of elements greater than b^h in b is less than one half of |a|+|b|.
Thus, we can discard the first h elements of a and the last h elements of b. Observe that, in this way, the length of at least one array has been halved (indeed, it is almost halved, since the median element/s is/are kept). We do not actually need to remove the elements of the arrays. We can just keep two indexes for each array, denoting the lower and upper bound of the range that can contain the global median.

//median of the elements of a with index between lo and hi
public double median(int[] a, int[] r) {
    return (a[(r[0] + r[1]) / 2] + a[(r[0] + r[1] + 1) / 2]) * 0.5;
}

//naive O(|a|+|b|) algorithm
public double naiveMedian(int[] a, int[] ra, int[] b, int[] rb) {
    int totalLength = ra[1] - ra[0] + 1 + rb[1] - rb[0] + 1;
    int pos1 = (totalLength - 1) / 2;
    int pos2 = totalLength / 2; //when totalLength is odd, pos1=pos2
    int i = ra[0];
    int j = rb[0];
    int k=0;
    double median = 0;
    while (k <= pos2) {
        if (i <= ra[1] && (j>rb[1] || a[i] <= b[j]) ) {
            if (k == pos1 || k == pos2) {
                median += a[i];
            }
            i++;
        } else {
            if (k == pos1 || k == pos2) {
                median += b[j];
            }
            j++;
        }
        k++;
    }
    if (pos1 != pos2) {
        median *= 0.5;
    }
    return median;
}

public double efficientMedian(int[] a, int[] b) {
    int[] ra = new int[]{0, a.length - 1}; //range of a
    int[] rb = new int[]{0, b.length - 1}; //range of b
    if (ra[1] < ra[0]) { //a is empty
        return median(b, rb);
    }
    if (rb[1] < rb[0]) { //b is empty
        return median(a, ra);
    }
    double ma = median(a, ra);
    double mb = median(b, rb);
    while (ma != mb && ra[1] - ra[0] > 1 && rb[1] - rb[0] > 1) {
        int delta = Math.min(ra[1] - ra[0], rb[1] - rb[0]) / 2;
        if (ma < mb) { //ignore the leftmost elements of a and the rightmost elements of b
            ra[0] += delta;
            rb[1] -= delta;
        } else { //ignore the rightmost elements of a and the leftmost elements of b
            rb[0] += delta;
            ra[1] -= delta;
        }
        ma = median(a, ra);
        mb = median(b, rb);
    }
    if (ma == mb) {
        return ma;
    }
    if (ra[1] - ra[0] <= 1) { //restrict the subarray of b to its elements in the middle
        return naiveMedian(a, ra, b, restrictRange(rb));
    } else { //rb[1] - rb[0] <= 1
        return naiveMedian(a, restrictRange(ra), b, rb);
    }
}

public int[] restrictRange(int[] r) {
    if (r[1] - r[0] <= 1) {
        return r;
    }
    int mid = (r[0] + r[1]) / 2;
    return new int[]{mid - 1, (r[1] - r[0]) % 2 == 0 ? mid + 1 : mid + 2};
}