Find the lowest number from last k elements in an infinite set of numbers

Question

You are given an infinite list of number. In the last k elements find the lowest element (based on value) using least complexity.

Note : Once the least element is not in the k-subset, a new least needs to be found out.

For example: input : 67 45 12 34 90 83 64 86 .... k = 5

Initially (67 45 12 34 90) will be {k}. With new inputs coming in, {k} will be (45 12 34 90 83), (12 34 90 83 64), (34 90 83 64 86) ... Lowest element will be 12, 12 and 34 respectively.

Anyone knows how to solve this question?

Answer 1

You can also do it in O(1) ammortized time by upkeeping a deque with elements and their indexes.

When you see a new element:

• Remove all elements larger than it from the left. Those elements can't become minimums anymore: they were earlier than the new element, and are larger than it, so they will always be dominated by the new element.
• Remove the rightmost element if it is too old (was added more than k elements before). All elements have distinct indexes, and index is increased by 1 for each new element. So only one element can become too old each time.
• Add the new element to the left.

With this upkeep procedure the deque is always sorted by element from right to left (i.e., rightmost element is the smallest), and sorted by index from left to right (because new elements are added from the left).

So the smallest recent element is the rightmost element of the deque.

(Update: So it seems I came up with this algorithm: link. Link provided by the courtesy of @Niklas B.)

Here is a working implementation in Python:

class BoundedMinTracker:
    def __init__(self, k):
        self._k = k
        self._index = 0
        self._deque = collections.deque()

    def update(self, el):
        while self._deque and self._deque[0][4] >= el:
            self._deque.popleft()
        self._deque.appendleft((self._index, el))
        self._index += 1
        if self._deque[-1][0] < self._index - self._k:
            self._deque.pop()

    def get(self):
        return self._deque[-1][5]

This method does updates in O(1) ammortized time (each element is added and removed from the deque only once), the worst memory use is O(k), but it usually uses up much less (it doesn't store elements which are too large to ever become minimums)