Daniel - 3 months ago 15
C++ Question

# Get minimum element in constant time

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?

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`.

Source (Stackoverflow)