# 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

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