## Sunday, May 23, 2010

### Count in a range in O(1)

Given n integers in the range 0 to k, answers any query about how many of the n integers fall into a range [a b] in O(1) time. Make your own assumptions and build your own indexing data structures.

PS: I was used to ask this question during my interviews. Now no longer ;-)

1. Only static arrays (when retrieval is done by the index, i.e. A) and perfect hash tables offer constant search time.

We will call the given n-sized array as array A. We allocate an array of k elements. We call this array B. Then

for (i = 0; i < k; i++) {
B[i] = number of elements from A >= i
}

Therefore array B will store:
B = number of elements from A >= 0
B = number of elements from A >= 1
B = number of elements from A >= 2
..
B[a] = number of elements from A >= a
B[b] = number of elements from A >= b

B[k-1] = number of elements from A >= k-1

Now the range query
"recover the number of elements >= a and <= b" is
answered by subtracting B[a]-B[b] with O(1) complexity.

2. 3. For preprocessing -
Make an array c[k] in which c[i] holds the number of elements less than or equal to i. This will take O(n+k).

Now to answer the query we need to calculate c[b]-c[a-1]