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

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