MediumLeetCode #146Stack & Queue

LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class with get and put operations in O(1) time complexity.

Constraints

1 <= capacity <= 3000, 0 <= key <= 10^4, 0 <= value <= 10^5, At most 2 * 10^5 calls will be made to get and put

Examples

Input: ["LRUCache","put","put","get","put","get","put","get","get","get"]\n[[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]

Output: [null,null,null,1,null,-1,null,-1,3,4]

Solution

Approach

Use hash map for O(1) lookup + doubly linked list for O(1) insertion/deletion at both ends. Move accessed items to front, evict from back.

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.order = collections.OrderedDict()
    
    def get(self, key):
        if key not in self.cache:
            return -1
        self.order.move_to_end(key)
        return self.cache[key]
    
    def put(self, key, value):
        if key in self.cache:
            self.order.move_to_end(key)
        self.cache[key] = value
        self.order[key] = None
        if len(self.cache) > self.capacity:
            oldest = next(iter(self.order))
            del self.cache[oldest]
            del self.order[oldest]

Complexity

Time:O(1)

Space:O(capacity)

Hints

1.Need O(1) lookup: use hash map
2.Need O(1) reorder: use doubly linked list
3.Move to front on access, evict from back

Asked at

Google