Another interesting problem that I saw today: *Given two sorted arrays, find their combined median* (median of the array formed by merging both the arrays). If the number of elements in the combined array is even, then the average of the two middle elements is the median.

# Tag Archives: median

# 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,

# Indexed Min-Priority Queue C++ implementation

A min-priority queue is an abstract data structure that supports efficient query of the minimum element in a list of elements, insertion of elements and deletion of the minimum element. It can be implemented as a min-heap, providing access to the minimum element in O(1), deletion of the minimum element in O(log N) and insertion in O(log N) where N is the number of elements in the heap.

# Median of a dynamic list

Here, I discuss the problem of maintaining the running median of a list when numbers are added and removed from the list. The straightforward solution of keeping the list sorted takes constant time per median calculation but linear time per addition/deletion. It would be too slow for our purpose.