LeetCode 146: LRU Cache

Use a doubly linked list to maintain elements in order of use and a hash map to keep track of elements present in the cache.

LRU cache summary card

Table of Contents
· Problem
· Approach
· Graphical Explanation
· Code Implementation
  ∘ Complexity
  ∘ Golang
  ∘ Python

Problem

Design a Least Recently Used(LRU) cache

• positive size capacity (no need to handle capacity == 0 edge case)
• evict policy: discard least recently used key when the cache is full
• implement two functions, get and put
  1. get: input → (key int); output → return value or -1 if key is not existed
  2. put: input → (key int, value int); update the value and the cache if key is existed
• The functions get and put must each run in O(1) average time complexity.

LRU Cache - LeetCode

Approach

We use doubly linked list to maintain elements in order of use. The least recently used key at the head and the most recently used key at the tail. This lets us access or remove elements at the head or tail in O(1) time. However, searching an element in a linked list runs in O(n) time because we have to traverse the whole linked list. A hash map can allow us to get a quick lookup. The hash map contains keys and refer to nodes in the doubly linked list. So we are able to access the node in O(1) time.

Graphical Explanation

• get(key)

get logic

• put(key, value)

put logic

• process

1

2

Code Implementation

Complexity

Time:
- get(key): O(1)
- set(key, value): O(1)

Space: O(c)
c: the capacity of the cache

Golang

Python

You can access the source code here.

Related story:

• LeetCode 460: LFU Cache