Find and keep minimum and maximum values in circular buffer structure

Question

The circular buffer is filled with data one value at a time. The buffer size is N elements (let's take 3 as an example). Is there an algorithm that allows you to always know what is the minimum and maximum of the data in the buffer at a given time?

Example:

Initial samples: {3 4 3 1 5 2 7 3 4 1}
Step 1: {[3] 4 3 1 5 2 7 3 4 1} -> The max of [3] is 3.
Step 2: {[3, 4] 3 1 5 2 7 3 4 1} -> The max of [3 4] is 4.
Step 3: {[3 4 3] 1 5 2 7 3 4 1} -> The max of [3 4 3] is 4.
Step 4: {3 [4 3 1] 5 2 7 3 4 1} -> The max of [4 3 1] is 4.
Step 5: {3 4 [3 1 5] 2 7 3 4 1} -> The max of [3 1 5] is 5.
Step 6: {3 4 3 [1 5 2] 7 3 4 1} -> The max of [1 5 2] is 5.
Step 7: {3 4 3 1 [5 2 7] 3 4 1} -> The max of [5 2 7] is 7.
Step 8: {3 4 3 1 5 [2 7 3] 4 1} -> The max of [2 7 3] is 7.
Done.
The output is therefore {3, 4, 4, 4, 5, 5, 7, 7}.

• greybeard: What about [7 3 4] & [3 4 1]?
• Dmitriy Yurov: It is step 9 and 10 :)

Answer 1

Though you don't specify it, you probably mean in constant time (otherwise just compute the minimum and maximum in linear time). I don't think that this is possible.

There is a nice procedure to compute sliding window extrema, described in "Efficient Dilation, Erosion, Opening and Closing Algorithms" by Joseph Yossi Gil & Ron Kimmel. It takes no more than 3 comparisons per element, whatever $N$, and requires extra buffers.

Unfortunately, it can only deliver all results on every other $N$ elements.

If you allow $\log(n)$ behavior, a min-max heap can do.

• Dmitriy Yurov: Yes, i told about constant time, log also would be nice to reach. Can you please share some code sample in any languages?
• user16034: Thirty seconds of Web lookup: github.com/d819r197/MinMax-Heap