Find the number of values between i & j(given as input) in an unsorted array in O(1) time

Question

Given an unsorted array $A$ of $n$ numbers and inputs $i$ and $j,ドル can we find the number of values $i<k<j$ in $A$ in O(1) time complexity by doing some preprocessing? An additional requirement is that the preprocessing should be $O(n)$ in both time and space.

I tried calculating an auxiliary array $B$ of size $M$ (where M is the maximum value in $A$) where $B[i]$ stores the number of elements smaller than $i$ in the given array. But for this the time and space complexities would be of order $O(M)$. Can one do better than that?

• Albert Hendriks: Do you have a O(1) solution that's O(n) in preprocessing even when the array is sorted?
• Evil: If this values are of known structure (integers from narrow band) you can do counting sort, then rank it (number of elements smaller than number in some index), but still it will need 2*O(logn) to find them. Any tree-like structure will need O(logn) to find indices. Still with very limited range you can preprocess it in form of LookUp Table to get O(1) but space requirements and preprocessing time will be greater.
• user12859: No, since you might have to read all of $i$ and $j,ドル which can take $\: \Omega \hspace{.02 in}(\log(n)) \:$ time. $\hspace{1.51 in}$
• Paras: Okay, got it. So unless the range of values is not of order O(n) it can't be done in linear time. Thanks !

Answer 1

No. If you could do that, then you could sort in $O(n)$ time, which seems unlikely to be possible (except in special cases, like where $M=O(n)$).

The sorting algorithm would be:

1. Preprocess $A$.

2. Let $t$ be the index of the smallest element in $A$. Let $i := A[t]$. Set $B[0] := t$.

3. For $u := 0,1,2,\dots,n-1$:

   • Let $j := A[u]$. If $u \ne t$: Count the number of array elements $k$ that satisfy $i < k < j$; call this number $m,ドル and set $B[m+1] := j$.

4. Output $B$.

The running time of this algorithm is $O(n)$. Also, $B$ is a sorted version of $A$: in each step of the for-loop, you find the index where element $j$ belongs, and put it in that place of $B$. The $O(1)$-time query lets you figure out the location where $j$ belongs in $O(1)$ time.

• Paras: Understood. Can't be done without knowing the range of values in linear time ! thanks a lot

Answer 2

In $A,ドル $rank( A[i] ) = \left\vert\left\{ j \in A : -\infty < j < A[i] \right\}\right\vert $

So you could sort the array by putting each element at its rank (up to duplicates, which can also be counted with 2 range queries), so if you could answer queries like this in $O(1)$ time and $O(n)$ preprocessing time and space, you would have an $O(n)$ sorting algorithm.

The latter does exist of course, but only under certain constraints, eg on the range of values.