Finding minimum number in a given array segment

Question

Let's say we have a large array of integers A. We want to answer to many queries like:

• Find the minimum between index 0 and 100
• Find the minimum between index 4 and 90
• ...

Example: A = {6, 1, 7, 5, 3}

• min between indexes 0 and 1 is 1
• min between indexes 2 and 3 is 5
• min between indexes 0 and 4 is 1

The obvious way of traversing the elements for each query and finding the minimum is not enough regarding performance. I somehow need to store the required information in one pass, and then answer to the queries in constant time. So the algorithm should not be quadratic. Something better than O(N * M) is needed. (N: array size, M: number of queries)

I tried but could not find how to do that. It must be something about finding and storing some sums and using them somehow. Any ideas? Thanks for reading.

Answer 1

Two options to consider:

1. O(n) precomputation and O(logn) per query
2. O(nlogn) precompuation and O(1) per query

The first works by recursively working out the minimum for all pairs at even locations, then all 4s at locations that are multiples of 4, then all 8s at all multiples of 8, and so on. Then whenever you want to access the minimum for a particular range, you break it into parts that you already have and compute the minimum of these.

For example, to find the minimum of elements 1..10 you use the minimum of 1 and 2..3 and 4..7 and 8..9 and 10.

The second works by working out the minimum for all pairs at ALL locations, then all 4s at ALL locations, then all 8s at ALL locations. When you have a particular range, you construct it as the minimum of two parts and compute the minimum of these two.

For example, to find the minimum of elements 1..10 you use the minimum of 1..8 combined with the minimum of 3..10.