Problem statement

https://binarysearch.com/problems/Last-Value-Map/

Solution

Keep stack of all keys. Also keep hash table of pairs key: value. When we asked getLast, pop from stack all old elements.

Complexity

It is amortized O(1) for all operations for time and O(n) for space.

Code

class LastValueMap:
    def __init__(self):
        self.d = {}
        self.stack = []

    def set(self, key, value):
        self.d[key] = value
        self.stack += [key]

    def remove(self, key):
        del self.d[key]

    def getLast(self):
        while self.stack[-1] not in self.d: self.stack.pop()
        return self.d[self.stack[-1]]