3

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.

Bhdr
  • 169
  • 3
  • 13
  • Can the initial pass be O(n^2)? – Sweeper Mar 10 '19 at 09:11
  • @Sweeper I guess you want to create a matrix of minimums. But the initial pass should also be better than O(n^2). Right now I'm trying a O(N logN) approach, I'll write here if it works. – Bhdr Mar 10 '19 at 09:21
  • Actually half a matrix is enough, but it's still O(n^2). – Sweeper Mar 10 '19 at 09:22
  • yes, you're right. – Bhdr Mar 10 '19 at 09:25
  • 3
    [algorithm - Range minimum query and update for intervals - Stack Overflow](https://stackoverflow.com/questions/30013113/range-minimum-query-and-update-for-intervals), [algorithm - Range Minimum Query approach (from tree to restricted RMQ) - Stack Overflow](https://stackoverflow.com/questions/14777743/range-minimum-query-on-o1-approach-from-tree-to-restricted-rmq), [java - Pseudo Range Minimum Query - Stack Overflow](https://stackoverflow.com/questions/19376893/pseudo-range-minimum-query) – user202729 Mar 10 '19 at 09:35
  • @user202729 thanks, I'll look at those. Very helpful comment. – Bhdr Mar 10 '19 at 09:55
  • @Bhdr look for RMQ tree or you can use MO's algorithm for the query in a simple array. – Rick_C137 Mar 11 '19 at 10:11
  • https://cp-algorithms.com/sequences/rmq.html this site seems to contain a lot of information. – Bhdr Mar 18 '19 at 10:45

2 Answers2

3

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.

Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75
-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)

Desperate
  • 1
  • 1