Search code examples
algorithmmaxmin

Incremental algorithm for maximum of last N entries in a series

Does anyone know of an efficient incremental algorithm for the maximum (or minimum) of the last n entries of an array?

By "efficient" and "incremental" I mean that when a new element is added to the array we do something smarter than just searching the last n entries for the maximum! Ideally it should be constant complexity O(1) with respect to n (and certainly < O(n)). Obviously each array entry can store one or more data to aid in the calculation. The computed maximum must be available for all array entries, not just the last entry.

Thanks

Solution

  • Here's an idea that gives you the min and max of the last n elements of the array in constant time and adding new elements is of O(log n) time complexity.

    1. Have a min and a max heap where you keep the last n elements of the array. These elements need to be nodes which you can reference later.
    2. Have a queue in the form of a linked list or any data structure where FIFO operations are of constant time complexity. Keep track of the last n elements in this queue. Each element of the queue holds a reference to the corresponding entries in the min and max heaps.
    3. Whenever a new element is added to the array do the following:
    • Add it to the min and max heaps: log n operations.
    • Enque the refernces to this new element in the queue: constant operation.
    • Deque the reference of the element that goes out of the n length window from the queue: constant operation.
    • remove that element from the min and max heap: log n operation.

    The min and max heaps give you the current min and max elements of the last n elements at any time in constant time.

    One possible optimization that wouldn't change the time complexity though is to combine the delete and add operations to a heap into one step. What you are going to do is to update the value of the reference that you want to delete from the heap with the value of the new element. Then run a swim and sink operation for the heap to hold its invariant. Then you will enque the dequed reference into the queue again, because it now holds the most recent value in the n length window.