find difference between max and min element within a range of an array

Say I got following array

a = [4 5 2 1 3 4]

and I want to find the difference between two elements (the max and min) excluding some consecutive elements.

For example, excluding the 2nd and 3rd so that I need to find the difference of max/min of:

  a = [4 1 3 4]

which in this case is

 diff = 4-1

Now I am looking for an efficient algorithm that can do this over and over. I was considering having a prefix and suffix but not sure how to move forward

Answer

So we have an array a of size N and M queries of this form: “Excluding the interval [L, R], what’s the difference between the max and min element in a?”. Consider we have an efficient way to query the min and max value on an arbitrary interval [X, Y], then we can use the following algorithm:

  1. Query min/max on the interval [0, L)
  2. Query min/max on the interval (R, N)
  3. Combine the min and max from both intervals
  4. Subtract the two

Later edit: I initially proposed a solution much more complicated than necessary. I will leave it if you are curious about other approaches, but here it is a simpler one.

As we know that we will always query only intervals of form [0, something) and (something, N), we could precompute the min/max values in linear time. Consider storing them like this:

min_from_left[i] = minimum item considering only items 0..i
min_from_right[i] = minimum item considering only items i..N
same for max

Now, the minimum value excluding the interval [L, R] is min(min_from_left[L-1], min_from_right[R+1]) (I omitted the bound checks). Thus, you can achieve O(N) for precomputing and O(1) per query.

The generic (but unnecessary approach)

To find the min/max value in a given interval you have plenty of options, it just depends what are your time and memory constraints and if you need updates or not:

Generally, you can obtain O(N + M * log N) time complexity if you need updates or O(N log N + M) if you don’t need them.

See more options here https://cp-algorithms.com/sequences/rmq.html