calculating max(min(A[i .. i+d])) in O(n) time O(n) memory

Question

I had an algorithm problem asking to get

max(min(A[i .. i+d]))

in

O (n)

time.

General Solution:

int max = 0;

for( i = 0; i< n-d; i++){

  int min = MX;

  for( j = i; j < i + d; j++)

     if(min > A[j])

       min = A[j];

  if(max < min)

     max = min;

}

printf("%d\n", max);

But it will take O(n x d) not O(n)

Better Solution: using Range_minimum_query

int max = 0;

for( i = 0; i< n-d; i++){

  int min = RMQ( i , i + d);

  if(max < min)

     max = min;

}

printf("%d\n", max);

It will take

O(log(d) * n)

as RMQ's average time is

log(d)

I thought this problem in my head about 15 days, but not renovation yet.
Could anyone solve this problem efficiently?

i/o data:

1<n<10^7 1<d<n

input : n = 10, d = 3, A[i] > 0

1, 3, 2, 4, 5, 6, 7, 8, 9, 10

result : 8 //= max(1, 2, 2, 4, 5, 6, 7, 8)

Recommended for you: Get network issues from WhatsUp Gold. Not end users.

Answer 1

Following the Range minimum query philosophy (which is good for random access), I would use a Double-ended queue (which is good for sequential access), which offers a average complexity of O(1) for all operations^*.

*_{except insertion/deletion)}

calculating max(min(A[i .. i+d])) in O(n) time O(n) memory

Sign up