Wednesday, November 22, 2006

Range Medians

Vitaliy of Google gave me the following nice algorithmic "puzzle" (admittedly via a proxy, and with my own twist).

Input: An array A[1,n] and a set of k possibly intersecting intervals [i,j] \in [1,n]. Output: For each interval [i,j], output median(A[i],A[i+1],...,A[j]). How fast can this problem be solved in the comparison model?

Spoiler: I can do this in O((n+k)polylog (n)). Anyone with O((n+k) log n) or even O(n+k) if that is possible?

5 Comments:

Anonymous Anonymous said...

I can do O(n log n + k log n log k). Whats the best you can can do?

A cute question, BTW.

11:32 PM  
Anonymous Anonymous said...

Sorry, n log n + k log^2 n log k.

12:34 AM  
Blogger metoo said...

I can do nlog^2 n + k.....

7:25 AM  
Anonymous Anonymous said...

O(n log k+ noise) seems o be possible.

2:08 AM  
Anonymous jef said...

I can do O(n log n + k log^2 n) using geometry.

11:38 PM  

Post a Comment

<< Home