searching for the maximum number between two indexes in an array of numbers

Question

I want to calculate the maximum number between two indexes in an array in an efficient way. I will be given a very large number of queries in each query I will be given indexes l and r where I need to find the maximum number between these two indexes

when I tried to solve that problem my solution had a time complexity of o((l-r)*q) where q is the number of queries

#include <bits/stdc++.h>
using namespace std;
int main()
        {
            int number = 1e6;
            vector <int> v(number);
            // the user should enter the elements of the vector
            for(auto &i : v) cin >> i;
            int number_of_queries=1e6;
            for(int i=0; i < number_of_queries; ++i)
            {
                int left_index,right_index,max_number = -1;
                //the user should enter the left and the right index (base zero)
                cin >> left_index >> right_index;
                //searching between the indexes for the maximum number between them
                for(int j=left_index ; j <= right_index; ++j) max_number=max(max_number,v[j]);
                //printing the number
                cout << max_number << "\n";
            }
        }

That's what I came up with

I want to know if there is a way to decrease the time complexity by maybe doing some operations on the array before starting

note that the array contains only positive numbers and it can contain the same number more than one time

Thank you in advance

Answer 1

If the array that is begin searched does not change, it could be efficient to create a look-up table to find the maximal element for each range. Since the table is 2-D, it will take a significant amount of time to populate, but there are some strategies to reduce the time it takes.

vector<vector<int>> lookUp();
for(int i=0;i<lookUp.size();i++){
   int max=v[i];
   for(int j=0;j<lookUp.size();j++){
      if(max<v[j])
         max=v[j];
      lookUp[i][j]=max;
   }
}

Answer 2

when I tried to solve that problem my solution had a time complexity of O((l-r)*q) where q is the number of queries

The only real way to reduce this is if the queries overlap. Then we need some way to store some kind of intermediate result (the max element of some given sub-range) so we can reuse it.

The general approach to reusing intermediate results is called dynamic programming, and the specific technique is to memoize a naive function, caching its result for later reuse.

Note that pre-computing maxima for fixed-size partitions adds a fixed (and possibly very large) overhead, but offers no guarantee about the hit rate - most of that effort could be wasted if we get a billion queries for the same small range.

In order to memoize results in this case, we need to chunk them. Only whole chunks can be easily reused.

So, your solution is:

1. choose a partition size - say we notionally divide our million elements into 100-element chunks

   • a small power of 2 like 16, 32 or 64 is probably optimal in practice, but I'm using round numbers for the example

2. write the naive max_in_chunk function (which, as mentioned in comments, is really just calling std::max_element)

   • now that this is a fixed-size chunk, there's a chance the compiler can vectorize it, which is always nice, but it's a secondary consideration to the memoization below

3. memoize that function with a wrapper, say memo_max_in_chunk, like

   // index must be a multiple of 100 or whatever chunk size we selected
   unsigned memo_max_in_chunk(size_t index)
   {
     static std::unordered_map<size_t, unsigned> memo;
   
     auto lookup = memo.insert({index, 0});
     auto &value = lookup.first->second; // value stored in map
     if (lookup.second)
     {
       // insertion succeeded => we don't have an existing result
       value = max_in_chunk(index);
     }
     return value;
   }
   

   It's a little hairy, so read the documentation until you understand it.

4. For your top-level loop, you now need to split the range [left_index, right_index] into three sections:

   1. the prefix, from left_index to the lowest multiple of 100 between left_index and right_index
   2. the suffix, from the highest multiple of 100 between left_index and right_index, to right_index
   3. a series of 100-element chunks in between them

   Now you can calculate the prefix_max and suffix_max naively, and call memo_max_in_chunk for each of the chunks between. Note that any of the prefix, suffix and chunk sections may be empty.

5. Finally just take the max of the prefix_max, suffix_max and all the chunk maxima.

Note that there are various optimizations that may improve the actual speed of this (like the vectorization mentioned, or, with some effort, using async evaluation of chunk maxima), but none of them change the complexity.

Even memoization won't improve the complexity if the queries are all smaller than our selected chunk size or never overlap, and there's not a lot we can do about that.