2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Do you have a O(1) solution that's O(n) in preprocessing even when the array is sorted? $\endgroup$ – Albert Hendriks Aug 13 '15 at 14:58
  • $\begingroup$ 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. $\endgroup$ – Evil Aug 13 '15 at 15:27
  • 1
    $\begingroup$ 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}$ $\endgroup$ – user12859 Aug 13 '15 at 19:35
  • $\begingroup$ Okay, got it. So unless the range of values is not of order O(n) it can't be done in linear time. Thanks ! $\endgroup$ – Paras Aug 14 '15 at 17:09
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Understood. Can't be done without knowing the range of values in linear time ! thanks a lot $\endgroup$ – Paras Aug 14 '15 at 17:11
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.