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:

- Query min/max on the interval
`[0, L)`

- Query min/max on the interval
`(R, N)`

- Combine the min and max from both intervals
- 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:

- Segment trees (support updates)
- Sparse tables (does not support updates)

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