LeetCode 146. LRU Cache

November 26, 2024

This took me a few days although it's only a medium! It is important to remember Python is pass-by-reference. I spent a lot of time debugging because I didn't mirror changes between previous and next nodes when moving a node between them. I was able to debug by creating a list of key-value pairs then printing the list after each operation.

Solution

Copy
1class Node:
2    def __init__(self, key=0, val=0, prev=None, next=None):
3        self.key = key
4        self.val = val
5        self.prev = prev
6        self.next = next
7
8class LRUCache:
9    def __init__(self, capacity: int):
10        self.capacity = capacity
11        self.size = 0
12        self.d = {}
13        self.l = None
14        self.start = None
15
16    def get(self, key: int) -> int:
17        if key in self.d:
18            node = self.d[key]
19            if node.prev and node.next:
20                node.prev.next = node.next
21                node.next.prev = node.prev
22            elif node.next:
23                self.start = node.next
24                self.start.prev = None
25            if self.l != node:
26                node.prev = self.l
27                self.l.next = node
28                self.l = self.l.next
29                self.l.next = None
30            return node.val
31        else:
32            return -1
33
34    def put(self, key: int, value: int) -> None:
35        if not key in self.d:
36            if self.size == self.capacity:
37                node = self.start
38                del self.d[node.key]
39                self.start = node.next
40                if self.start:
41                    self.start.prev = None
42                self.size -= 1
43            if self.l:
44                self.l.next = Node(key, value, self.l)
45                self.l = self.l.next
46            if not self.start:
47                self.start = Node(key, value)
48                self.l = self.start
49            self.d[key] = self.l
50            self.size += 1
51        else:
52            node = self.d[key]
53            if node == self.start and self.start.next:
54                self.start = self.start.next
55                self.start.prev = None
56            if node.prev and node.next:
57                node.prev.next = node.next
58                node.next.prev = node.prev
59            if node != self.l:
60                node.prev = self.l
61                self.l.next = node
62            node.val = value
63            node.next = None
64            self.l = node
65
66
67
68# Your LRUCache object will be instantiated and called as such:
69# obj = LRUCache(capacity)
70# param_1 = obj.get(key)
71# obj.put(key,value)

Time complexity for get and put operations are O(n) = 1 and space complexity is O(n) due to the dictionary holding each element.

LeetCode 86. Partition List

LeetCode 105. Construct Binary Tree from Preoder and Inorder Traversal