CODEWITHSUNDEEP
javaalgorithmdata-structuresarray-algorithms
Bhdr
Bhdr

Reputation: 169

Finding minimum number in a given array segment

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

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

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.

Upvotes: 3

Views: 701

Answers (2)

Desperate
Desperate

Reputation: 1

For each question make an "solution", a "min" and a "max"

Then as you pass to the next element of the array , if you reach the Index==min of a question, solution=the number of that Index. And as long as you don't reach the max, you compare solution with the number in that Index and actualice solution. (Ok I realized as i posted that this is n*m, sorry)

Upvotes: -1

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

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.

Upvotes: 3

Related Questions