Daniel 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?

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.

Comments