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:


create 1 min candles of prices, which will reduce the storage but then wont be exactly correct
store the top K elements with their price and timestamps and update this list according to the current timestamp
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.