Kth maximum element in unsorted collection

Finding the Kth maximum element in an unsorted array doesn’t seem to be a big deal. Because, we know that finding the maximum and if we keep on eliminating the largest element from the array. And this we will take us to the Kth maximum element in an array. But this solution is of order O(n²). Can it be done in linear way?

Yes. Well, almost.

Have a look at the following method written in Java.

public static int findKthMax(List input, int k) {
	if (input != null && input.size() > 0) {
		int element = input.get(0);
		List largerThanElement = new ArrayList();
		List smallerThanElement = new ArrayList();

		for (int i = 1; i < input.size(); i++) {
			if (element < input.get(i)) {
				largerThanElement.add(input.get(i));
			} else {
				smallerThanElement.add(input.get(i));
			}
		}

		if (largerThanElement.size() == k - 1) {
			return element;
		} else if (largerThanElement.size() < k - 1) {
			return findKthMax(largerThanElement, k - largerThanElement.size() - 1);
		} else if (largerThanElement.size() >= k) {		 
			return findKthMax(largerThanElement, k);
		}
		return element; // To satisfy the crazy compiler
	} else {
		throw new IllegalArgumentException();
	}
}

Generalizing into an algorithm

Calling FindKthMax(int[] input, int k)

1. Pick randomly a pivot a from input, lets call the selected pivot element – a.

2. Partition the n numbers into two sets:

* S – all the numbers smaller than a

* L – all the numbers larger than a

3. If |L| = k – 1 then a is the required K-median. Return a.

4. If |L| < k – 1 then the K-median lies somewhere in S. Call recursively to FindKthMax( S, k- |L| – 1 )

5. Else, call recursively  FindKthMax( L, k ).

Extending the solution to solve other problems:

The algorithm can be extended to find the median as well.
Q. Find the median of an array A.
A. If length of A is odd, the median would be FindKthMedian(a.length/2 + 1, input).
If the length of A is even, the median [FindKthMedian(a.length/2, input) + FindKthMedian(a.length/2 + 1, input)] / 2

And the problems are beautifully solved in linear order on n.

No. of Step Calculation in an Algorithm

There was a time when the processor were just starting to explore their potential. Then code optimization made a huge difference in the performance of the code. But, today most programmers take the optimization for granted as the compilers are smarter and the processors run like they have fire on their ass. But, to be a good programmer, one should always stick to the roots of programming.

Let their be three arrays, A, B and C of equal lengths n. And an operation is to be performed say,

for(i = 0; i < n; i++)
    A[i] = B[i] + C[i]

Everybody knows that the program is of O(n) complexity. But, what struck me hard is, people say that n statements will be executed for this. This is because, those morons have never been exposed to assembly like programming. This is because of the driver’s mindset, instead of the mechanic’s mindset.

For those who don’t know, your coding language will in turn call the instructions of the processor as:

1. i = 0
2. if i >= n jump to 9
3. x = A[i]
4. y = B[i]
5. z = x + y
6. C[i] = z
7. i = i + 1
8. jump to step 2
9. end

Here, i, x, y, z are values stored in processor registers.

• Step 3 to 8 can be assumed to be the part of the iteration and will be executed n times.
• Step 2 will be executed n + 1 times. Last execution will be the step which will allow the jump to step 9. 
• Thus, total steps required – 6n + n + 1 + 2 = 7n + 3, which of course is O(n)
• Or, total steps is 2 + n(b + 3) where b is the number of steps in for loop excluding increment of counter and jump.

Greatest Common Divisor: Euclid Style

Euclid out of nowhere proposed this algorithm which calculates the greatest common divisor of two numbers. The simplest way of calculating the GCD is probably the simple prime factorization method. But, Euclid was no common chap. He devised a way which calculates the GCD recursively. The idea was to simplify the problem each time, preserving the GCD. Lets discuss the algorithm, in order to understand it-

getGCD(n, m) {
    while(n % m != 0) {
        r = n % m;
        n = m;
        m = r;
    }
    return m;
}

1. The next iteration is always getGCD(m, n % m), the thing to keep in mind here is that the GCD for (n, m) is same as (m, n % m).
2. Also note, that sum of the two numbers in each iteration reduces to <= 3/2 of its value. log (m + n) base 3/2. i.e. The sum is bound to 3/2.

Proof of the 3/2 fact –

Let the input be p and q, the input for next iteration be p’ and q’.
here, q’ = p % q <= q
   => p’ = q
   => p’ + q’ = remainder + divisor <= dividend (p) 

now, p’ + q’ + (p’ + q’) + (p’ + q’) <= q + q + 2p
   => 3(p’ + q’) <= 2(p + q)
   => (p + q)/(p’ + q’) = 3/2

Hence proved.

I am still confused, how he thought of this algorithm, but hats off to Euclid.