If you want to make money online : Register now

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

, , No Comments
Problem Detail: 

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?

Asked By : Paras

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45234

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback