Problem of the day: Matrix median

So here’s an interesting problem: Given an NxM integer matrix in which each row is sorted, find the overall median of the matrix assuming N*M is odd. For example,

Continue reading

Advertisements

Randomized selection algorithm

The problem is to find the ith order statistic (i.e., ith smallest element) in an input array. This algorithm is a modification of quicksort and takes time O(n), on average, on an input array of size n.

Continue reading