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

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

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.