yrazlik
yrazlik

Reputation: 10777

Finding number of integers within a range

I am reading introduction to algorithms 3rd edition and i ran into the following: Suppose that we are given n integers in the range 0 to k and we want to find out how many of these integers are in the range [a,b] for given integers a and b. It has the brute solution, but then it says that by a preprocessing phase on the input, this query can be completed in Θ(1) time, and this proprocessing phase takes O(n+k) time. I am thinking about sorting the integers, but sorting at least takes O(nlogn) time, which exceeds O(n+k). What can be done for the preprocessing phase? Thanks

Upvotes: 1

Views: 1688

Answers (1)

Knoothe
Knoothe

Reputation: 1218

Since the numbers are in range [0,k] you can use counting sort to sort them in O(n+k) time.

Once you have the counts, you can take the prefix sums of that count array, which will tell you the number of numbers in the range [0, a]. O(k) time.

Using that you can answer queries for [a,b] by taking the appropriate difference, in O(1) time.

Upvotes: 5

Related Questions