Puzzle via blogs
Researchers in histogram construction (yes, there are several) will recognize the following problem: given an array A of size N, for each interval [l,r] in [1,N],
determine the median of items in the interval A[l],A[l+1],....,A[r]. How quickly can one solve this problem? I had a few playful moments a couple of weeks ago and wrote this note, but with more play time, one should have a simpler, O(N^2) time algorithm. Further, one should be able to do this using o(N^2) space, not counting the output size. No approximations please. Enjoy!