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)

Could you be more specific? Maybe an input/output example? I don't fully understand the task — Marco, Sep 22 '17 at 14:54
Look at [Range_minimum_query](https://en.wikipedia.org/wiki/Range_minimum_query). — Jarod42, Sep 22 '17 at 14:55
@Jarod42 Does it support O(n+d)? I think it will take o((log d) * n) — artgb, Sep 22 '17 at 14:58
For fixed sized ranges there is this research paper. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.29.4547 — Raymond Chen, Sep 22 '17 at 15:06
RMQ is for random access, for sequentual access there is better method: https://stackoverflow.com/questions/12190184/can-min-max-of-moving-window-achieve-in-on/12195098#12195098 — MBo, Sep 22 '17 at 16:23
There's [this algorithm](https://people.cs.uct.ac.za/~ksmith/articles/sliding_window_minimum.html) with amortized O(n) running time. Whatever you do, make sure to cite your sources when you turn in the assignment, so you aren't guilty of academic dishonesty. — Raymond Chen, Sep 22 '17 at 17:15

score 1 · Accepted Answer · answered Sep 22 '17 at 16:49

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)}

answered Sep 22 '17 at 16:49

gsamaras

71,951
46
188
305

Thanks for your answer, Could you provide full answer? – artgb Sep 22 '17 at 16:51

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

1 Answers1