How to find array elements that fall in a given interval?

Question

This is an interview question.

Given an array of integers and a stream of intervals (pairs of integers), find the elements of the array that fall into each interval of the stream. What array preprocessing would you use?

Answer 1

One option is to pre-process the array by sorting it in ascending order. Once you do this, you can find all the elements that fall into the interval by doing two binary searches on the sorted array - one to find the first element that is greater than or equal to the beginning of the interval, and one to find the last element not exceeding the end point of the interval and then iterate over the array by the output of all elements in this range.

It takes O (n log n) time to preprocess if you use a standard sorting algorithm like quicksort or heapsort, but you can do it in O (n log U) if you use radix sort (here U is the largest integer in the range). Then the queries take time O (log n + k), where n is the number of elements and k is the number of elements within the range.

If you want a fantasy, you can speed it up exponentially using van Emde Boas tree , a specialized data structure for storing integers.If the largest integer value you work with is U, then you can build the structure in time O (n log log U), and then search for the range of endpoints in O time (log log U). You can then find all the items in the O (log log U) time range apiece by providing the O (k log log U) algorithm to find all matches within the range.

Hope this helps!

Answer 2

Sort the array, then do a binary search to find the indices of the first element in the array, which is greater than the starting interval, and then again find the first element, which is less than the end of the interval, and return all integers between them. This will be O(log N) for each search, where N is the number of integers.

Answer 3

The answer depends on your requirements:

how many intervals did you say M?

Of course, the use of M * O (N logN) is redundant, especially when M is large, as well as intervals.

Another approach: using O (N) extra space.

 prefix[i] = number of numbers in range 0 to i 

Can be done in O (N) time.

Now you need O (1) time for each request:

 query[l,r] = prefix[r] - prefix[l - 1] + 1 

therefore, the total time complexity of O(N logN + M)

Answer 4

How about indexing an array according to its elements?

 for (i in original_array) indexed_array[original_array[i]] = original_array[i] for (j in stream) { for (k=stream[j][0]; k<=stream[j][1]; k++) if (indexed_array[k]) return indexed_array[k] } 

Or put indices instead of integers:

 for (i in original_array) indexed_array[original_array[i]] = i