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?
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?
posted by metoo at 11:05 AM
5 Comments:
I can do O(n log n + k log n log k). Whats the best you can can do?
A cute question, BTW.
Sorry, n log n + k log^2 n log k.
I can do nlog^2 n + k.....
O(n log k+ noise) seems o be possible.
I can do O(n log n + k log^2 n) using geometry.
Post a Comment
<< Home