Daniel - 8 months ago 45

C++ Question

Lets say I have an array A of size n, where 0 <= A[i] <= n.

Lets say I have 2 arrays Forward and Backward, size n, where:

`Forward[i] = index j where`

A[j] = min(A[i], A[i+1], ..., A[n-1])

and

`Backward[i] = index j where`

A[j] = min(A[i], A[i-1], ..., A[0])

My question is:

- given A, Forward and Backward
- given 2 indexes
*l*and*r*

Can I discover the index k such that A[k] = min(A[l], A[l+1], ..., A[r]) in constant time?

Answer

No. Atleast not in O(1) time. A counter example is as follows. `0-based`

indexing is used here. Let

```
index = {0, 1, 2, 3, 4, 5, 6, 7, 8}
A = {1, 3, 5, 7, 9, 6, 4, 2, 0}
Forward = {8, 8, 8, 8, 8, 8, 8, 8, 8}
Backward = {0, 0, 0, 0, 0, 0, 0, 0, 8}
```

Now, if I ask you to get the index of the minimum value in range `[3, 7]`

, how will you do it?

Basically they will be of no use to find in the range [a, b]

if

`forward[a] > b`

and`backward[b] < a`

.