Maximum & Minimum of any subarray in constant time

Question

I am a computer science engineering student and I came to this problem in many tasks.

I am given an array of size with values and then asked a number of queries .

In each query I am given two indices where .

I believe, there is a way to answer this queries in if some pre-processing is done.

I have to do it in .

I have been on this problem for many days, but I can not get it at all.

Answer 1

This problem is known as "range minimum query". It is well-studied, and if you Google that, you will end up at the well-known, very clever, and pretty complicated data structure that meets your requirements, requiring O(N) space and preprocessing time.

Here I'll provide a much simpler solution that performs better in practice whenever your array contains less than 2⁶⁴ items... i.e., always.

I'll only talk about finding the minimum, but of course finding the maximum requires a similar structure.

Like the well-known data structure, it uses this one as a component:

Simple O(N log N) space solution

Given an array A of N items, let M = ceil(log₂ N).

Make a matrix W of size NxM and, for each (i,j) with 0 < i < N and 1 < j < M, assign W[i][j] to the index of the minimum value amongst the 2^j elements starting at A[i], stopping at the end of the array.

So now, for every window of size 2^j, we have the index of its minimum value. Since every subarray is exactly covered by at most 2 overlapping windows, we can easily find the minimum value in any subarray by checking those 2 windows and picking the lower of their 2 minimums.

Initializing this data structure can be done in constant time per item. If you do the smaller window sizes first, then each window minimum can be found by merging the results for 2 smaller windows.

This solution requires storing log N indexes per array item.

O(N) space solution

To make a solution fit into O(N) space, we need to use the preceding data structure at 2 levels:

1. Divide the input into blocks of 64 elements. Pick the smallest item in each block as its representative. Implement the O(N log N) solution for the array of representatives. Given that N < 2⁶⁴, this requires storing fewer than 64 indexes per block, which is at most one index per item -- O(N)
2. Implement the O(N log N) solution separately for the 64 items in each block. This requires storing up to 6 indexes per item, for sizes 64, 32, 16, 8, 4, 2. But you only need 6 bits or less per index. The index for window size 2 only takes 1 bit. Those 6 indexes can therefore be packed into one 32-bit word per item -- O(N) again. (Implementation Note: still cut the windows off at the array end, not the block ends)

Now, we've spent only 8 or 12 bytes per item (depending on whether array indexes are 32 or 64 bits), and we can easily answer any range-minimum query in constant time:

• Check at most 2 overlapping windows of block representatives to find the minimum value within all complete blocks covered by the query;
• Check at most 2 partial block windows to cover the remainder of the query;
• return the minimum value found.