# sliding window maximum

I have a stream of tuples arriving in the following form: (timestamp,price). There is no pattern in the arrival of these data points (number of data points per minute is random). I need to be able to return the maximum price in the last hour at any point of time. What is the most efficient algorithm in terms of time complexity and space complexity separately to do this ? I thought of the following:

1. create 1 min candles of prices, which will reduce the storage but then wont be exactly correct
2. store the top K elements with their price and timestamps and update this list according to the current timestamp
• What's a "min candle"? – D.W. Dec 16 '19 at 2:14
• (I read one minute candle - no idea how to interpret candle.) – greybeard Dec 16 '19 at 6:43
• Are the tuples specified to arrive in order of non-decreasing timestamps? – greybeard Dec 16 '19 at 6:45
• A candle means summary stats for one minute data, this is not an exact solution but an approximate one – Aman Jakhar Dec 16 '19 at 6:56
• They arrive in realtime so yes non decreasing timestamps – Aman Jakhar Dec 16 '19 at 6:56

In the worst case, there is no algorithm with better space complexity than storing all data points from the past hour. So, I think you should focus on optimizing time complexity. A reasonable data structure would be to store them in a balanced binary tree, keyed on timestamp, where each node is augmented with the maximum price over all descendants of that node. This achieves $$O(n)$$ space, if there are $$n$$ data points within the past hour, and $$O(\log n)$$ time per data point that you receive.

You will have to store one hour's worth of tuples. You can see this in the worst case of a series of descending prices over an hour. Say they were to come in one a minute starting at a price of 60. Then the first maximum would expire in one minute, then the second in the second minute and so on.

You should store the data in time order and only keep one hour's worth of tuples (using a FIFO queue). You haven't specified if timestamps are strictly in order as they come in. If not, then they will have to be kept sorted O(nlogn) - in which case its more efficient to store the tuples in order of price, then reading off the maximum is a case of reading the tuple at the end of the list.

However the data is sorted, you will have to do a linear scan either to find the maximum price (time ordered) or to remove tuples over one hour old (price ordered).

If time ordered you could keep scans of the data down by keeping track of the current maximum price and its position in the list. You compare each new tuple's price with the current maximum and if it's higher then this becomes the new maximum.

When the current maximum falls off the list (its age is greater than an hour), you do a linear scan to find the new maximum. This means doing a linear scan once an hour in the worst case.

If price ordered you can keep scans down by keeping track of the oldest timestamp and doing a linear scan for the next oldest when it expires.

For time complexity, it partly depends on where you want to improve the time. You could consider a FIFO where each record has the price and the timestamp and also something else: the largest price over every item that is as/more recent. This would mean an $$O(n)$$ operation for each batch of items that is inserted, but it would improve the time for fetching the maximum price, since you could peek at the front of the line, and pull off a few obsolete items (older than an hour) until you find an item no more than an hour old, and then the max price in that item is the value you want.

Or you could make each record contain the max price over all that is at least as old. In this case, to retrieve the max price over hour, it is an $$O(1)$$ operation if no old items need to be removed from the FIFO, but otherwise all the old items need to be purged and the max prices recomputed in $$O(n)$$.

But maybe what you want is a specialized B tree, in which each node contains as an extra field the largest price in the whole subtree. Whenever the B tree is restructured, all subtrees that are altered will require those fields to be recomputed. In the worst case, all deletions are happening at one end of the tree and all insertions at another... so I don't know if some of the extra balancing work of the tree is significant. After deleting an obsolete item, it would take $$O(\log n)$$ operations to update the nodes above it. Once a tree is purged of data more than an hour old (and all new data is added), only the tree root needs to be consulted to determine the maximum price in this case.

In all these instances, the best scheme with respect to time might depend on how frequently that price question needs to be answered compared to how frequently new data needs to be input.

I think the space complexities for these approaches are $$O(n)$$. With regard to space-saving you might think of having a data structure for each period of 10 minutes like so: 1:00-1:09; 1:10-1:19; etc. Then each price record only needs to contain a timestamp relative to the 10 minute threshold. If you precision is 1 sec, then each record only needs to distinguish which of 600 seconds the price is mamixum over. If it takes a second or more to compute the maximum anyway, then it should be precise enough to eliminate data that is 3600 +/- 1 second old.

The time precision is important. Is it close enough to count things minute by minute? If so, then you only need one record for each minute, and you can update the last minute's record with any new data if there are multiple data coming in for that minute. This will affect your storage by a significant factor, but this factor would only be $$O(1)$$.