LRU Cache

Problem Statement

Design a data structure that follows the constraints of a Least Recently Used (LRU) Cache.

Implement the LRUCache class:

LRUCache(int capacity) — Initialize the LRU cache with positive size capacity.
int get(int key) — Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) — Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity, evict the least recently used key.

Both get() and put() must run in O(1) average time complexity.

Examples

Operation	Capacity	State Before	State After	Return
`LRUCache(2)`	2	`{}`	`{}`	—
`put(1, 1)`	2	`{}`	`{1: 1}`	—
`put(2, 2)`	2	`{1: 1}`	`{1: 1, 2: 2}`	—
`get(1)`	2	`{1: 1, 2: 2}` (1 is recent)	`{1: 1, 2: 2}`	`1`
`put(3, 3)`	2	`{1: 1, 2: 2}`	`{1: 1, 3: 3}` (2 evicted)	—
`get(2)`	2	`{1: 1, 3: 3}`	`{1: 1, 3: 3}`	`-1`
`put(4, 4)`	2	`{1: 1, 3: 3}`	`{3: 3, 4: 4}` (1 evicted)	—
`get(1)`	2	`{3: 3, 4: 4}`	`{3: 3, 4: 4}`	`-1`
`get(3)`	2	`{3: 3, 4: 4}` (3 is recent)	`{3: 3, 4: 4}`	`3`
`get(4)`	2	`{3: 3, 4: 4}` (4 is recent)	`{3: 3, 4: 4}`	`4`

Constraints

1 <= capacity <= 3000
0 <= key <= 10^4
0 <= value <= 10^5
At most 3 × 10^4 calls to get() and put().

Real-World Applications

Complexity Comparison

Approach	Time (get/put)	Space	Eviction	Best When
Hash Map + Doubly Linked List	O(1) / O(1)	O(capacity)	Constant-time node removal	General case — full control, fast in all scenarios
OrderedDict / LinkedHashMap	O(1) / O(1)	O(capacity)	Constant-time via language feature	You trust built-in ordered structures, cleaner code
HashMap + Priority Queue	O(log n) / O(log n)	O(capacity)	Log-time priority updates	Not recommended; slower than the above

Which approach should you learn first?

Pick Hash Map + Doubly Linked List if you want to understand the mechanics and impress in interviews.
Pick OrderedDict if you are practicing a language’s built-in data structures and want cleaner code.

Best For Interviews

Hash Map + Doubly Linked List

O(1) time · O(capacity) space

Cleanest Code

OrderedDict / LinkedHashMap

O(1) time · O(capacity) space

Approach 1: Hash Map + Doubly Linked List (Recommended)

★ Recommended

Combine a hash map for O(1) lookups with a doubly linked list to track access order. The most recently used item is kept at the head, and the least recently used item is at the tail (ready to evict).

The key insight is that moving a node to the head and removing a node from the tail are both O(1) operations when you have pointers.

⏱ Time O(1) Hash lookup + list pointer ops 💾 Space O(capacity) Hash + linked list nodes

Step-by-step Example

Sequence: LRUCache(2) → put(1,1) → put(2,2) → get(1) → put(3,3) → get(2)

Step	Operation	Cache State	DLL Order (head→tail)	Action
1	`put(1, 1)`	`{1: 1}`	`1`	Insert 1 at head
2	`put(2, 2)`	`{1: 1, 2: 2}`	`2 → 1`	Insert 2 at head
3	`get(1)`	`{1: 1, 2: 2}`	`1 → 2`	Move 1 to head (accessed)
4	`put(3, 3)`	`{1: 1, 3: 3}`	`3 → 1`	Insert 3, evict 2 (least recent)
5	`get(2)`	`{1: 1, 3: 3}`	`3 → 1`	Return -1 (2 not in cache)

Step 1 of 5 Target: capacity

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

class DLLNode:
    key, value, prev, next

class LRUCache:
    capacity, cache (HashMap), head, tail (dummy nodes)

    get(key):
        if key not in cache:
            return -1
        node = cache[key]
        moveToHead(node)  // Mark as recently used
        return node.value

    put(key, value):
        if key in cache:
            node = cache[key]
            node.value = value
            moveToHead(node)
        else:
            if cache.size >= capacity:
                removeTail()  // Evict least recently used
            node = new DLLNode(key, value)
            cache[key] = node
            addToHead(node)

    moveToHead(node):
        removeNode(node)
        addToHead(node)

    removeNode(node):
        node.prev.next = node.next
        node.next.prev = node.prev

    addToHead(node):
        node.next = head.next
        node.prev = head
        head.next.prev = node
        head.next = node

    removeTail():
        node = tail.prev
        removeNode(node)
        cache.remove(node.key)

Solution Code

from typing import Optional


class DLLNode:
    def __init__(self, key: int = 0, value: int = 0):
        self.key = key
        self.value = value
        self.prev: Optional['DLLNode'] = None
        self.next: Optional['DLLNode'] = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}  # key -> node
        self.head = DLLNode()  # dummy head
        self.tail = DLLNode()  # dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._move_to_head(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._move_to_head(node)
        else:
            if len(self.cache) >= self.capacity:
                self._remove_tail()
            node = DLLNode(key, value)
            self.cache[key] = node
            self._add_to_head(node)

    def _move_to_head(self, node: DLLNode) -> None:
        self._remove_node(node)
        self._add_to_head(node)

    def _remove_node(self, node: DLLNode) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_head(self, node: DLLNode) -> None:
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def _remove_tail(self) -> None:
        node = self.tail.prev
        self._remove_node(node)
        del self.cache[node.key]


# Test
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))  # 1
cache.put(3, 3)
print(cache.get(2))  # -1
cache.put(4, 4)
print(cache.get(1))  # -1
print(cache.get(3))  # 3
print(cache.get(4))  # 4

#include <iostream>
#include <unordered_map>
#include <list>

class LRUCache {
private:
    int capacity;
    std::unordered_map<int, std::pair<int, std::list<int>::iterator>> cache;
    std::list<int> order;

public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1;
        }
        order.erase(cache[key].second);
        order.push_back(key);
        cache[key].second = std::prev(order.end());
        return cache[key].first;
    }

    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            order.erase(cache[key].second);
            order.push_back(key);
            cache[key] = {value, std::prev(order.end())};
        } else {
            if (cache.size() >= (size_t)capacity) {
                int lru_key = order.front();
                order.pop_front();
                cache.erase(lru_key);
            }
            order.push_back(key);
            cache[key] = {value, std::prev(order.end())};
        }
    }
};

int main() {
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    std::cout << cache.get(1) << std::endl;  // 1
    cache.put(3, 3);
    std::cout << cache.get(2) << std::endl;  // -1
    cache.put(4, 4);
    std::cout << cache.get(1) << std::endl;  // -1
    std::cout << cache.get(3) << std::endl;  // 3
    std::cout << cache.get(4) << std::endl;  // 4
    return 0;
}

import java.util.HashMap;

class DLLNode {
    int key;
    int value;
    DLLNode prev;
    DLLNode next;

    DLLNode(int key, int value) {
        this.key = key;
        this.value = value;
    }

    DLLNode() {
        this(0, 0);
    }
}

public class LRUCache {
    private int capacity;
    private HashMap<Integer, DLLNode> cache;
    private DLLNode head;
    private DLLNode tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.head = new DLLNode();
        this.tail = new DLLNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        DLLNode node = cache.get(key);
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            DLLNode node = cache.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            if (cache.size() >= capacity) {
                removeTail();
            }
            DLLNode node = new DLLNode(key, value);
            cache.put(key, node);
            addToHead(node);
        }
    }

    private void moveToHead(DLLNode node) {
        removeNode(node);
        addToHead(node);
    }

    private void removeNode(DLLNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addToHead(DLLNode node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void removeTail() {
        DLLNode node = tail.prev;
        removeNode(node);
        cache.remove(node.key);
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));  // 1
        cache.put(3, 3);
        System.out.println(cache.get(2));  // -1
        cache.put(4, 4);
        System.out.println(cache.get(1));  // -1
        System.out.println(cache.get(3));  // 3
        System.out.println(cache.get(4));  // 4
    }
}

class DLLNode {
    constructor(key = 0, value = 0) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
        this.head = new DLLNode();
        this.tail = new DLLNode();
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    get(key) {
        if (!this.cache.has(key)) {
            return -1;
        }
        const node = this.cache.get(key);
        this.moveToHead(node);
        return node.value;
    }

    put(key, value) {
        if (this.cache.has(key)) {
            const node = this.cache.get(key);
            node.value = value;
            this.moveToHead(node);
        } else {
            if (this.cache.size >= this.capacity) {
                this.removeTail();
            }
            const node = new DLLNode(key, value);
            this.cache.set(key, node);
            this.addToHead(node);
        }
    }

    moveToHead(node) {
        this.removeNode(node);
        this.addToHead(node);
    }

    removeNode(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    addToHead(node) {
        node.next = this.head.next;
        node.prev = this.head;
        this.head.next.prev = node;
        this.head.next = node;
    }

    removeTail() {
        const node = this.tail.prev;
        this.removeNode(node);
        this.cache.delete(node.key);
    }
}

const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1));  // 1
cache.put(3, 3);
console.log(cache.get(2));  // -1
cache.put(4, 4);
console.log(cache.get(1));  // -1
console.log(cache.get(3));  // 3
console.log(cache.get(4));  // 4

use std::collections::HashMap;
use std::rc::Rc;
use std::cell::RefCell;

type NodeRef = Rc<RefCell<Node>>;

struct Node {
    key: i32,
    value: i32,
    prev: Option<NodeRef>,
    next: Option<NodeRef>,
}

impl Node {
    fn new(key: i32, value: i32) -> Self {
        Node {
            key,
            value,
            prev: None,
            next: None,
        }
    }
}

struct LRUCache {
    capacity: usize,
    cache: HashMap<i32, NodeRef>,
    head: NodeRef,
    tail: NodeRef,
}

impl LRUCache {
    fn new(capacity: i32) -> Self {
        let head = Rc::new(RefCell::new(Node::new(0, 0)));
        let tail = Rc::new(RefCell::new(Node::new(0, 0)));

        head.borrow_mut().next = Some(tail.clone());
        tail.borrow_mut().prev = Some(head.clone());

        LRUCache {
            capacity: capacity as usize,
            cache: HashMap::new(),
            head,
            tail,
        }
    }

    fn get(&mut self, key: i32) -> i32 {
        if let Some(node) = self.cache.get(&key) {
            let node = node.clone();
            let value = node.borrow().value;
            self.move_to_head(node);
            value
        } else {
            -1
        }
    }

    fn put(&mut self, key: i32, value: i32) {
        if let Some(node) = self.cache.get(&key) {
            let node = node.clone();
            node.borrow_mut().value = value;
            self.move_to_head(node);
        } else {
            if self.cache.len() >= self.capacity {
                self.remove_tail();
            }
            let node = Rc::new(RefCell::new(Node::new(key, value)));
            self.cache.insert(key, node.clone());
            self.add_to_head(node);
        }
    }

    fn move_to_head(&mut self, node: NodeRef) {
        self.remove_node(node.clone());
        self.add_to_head(node);
    }

    fn remove_node(&mut self, node: NodeRef) {
        let mut node_mut = node.borrow_mut();
        if let Some(prev) = &node_mut.prev {
            if let Some(next) = &node_mut.next {
                prev.borrow_mut().next = Some(next.clone());
                next.borrow_mut().prev = Some(prev.clone());
            }
        }
    }

    fn add_to_head(&mut self, node: NodeRef) {
        let mut node_mut = node.borrow_mut();
        let head_next = self.head.borrow_mut().next.take();

        node_mut.prev = Some(self.head.clone());
        node_mut.next = head_next.clone();

        if let Some(next) = head_next {
            next.borrow_mut().prev = Some(node.clone());
        }
        self.head.borrow_mut().next = Some(node);
    }

    fn remove_tail(&mut self) {
        let tail_prev = self.tail.borrow_mut().prev.clone();
        if let Some(node) = tail_prev {
            let key = node.borrow().key;
            self.remove_node(node);
            self.cache.remove(&key);
        }
    }
}

fn main() {
    let mut cache = LRUCache::new(2);
    cache.put(1, 1);
    cache.put(2, 2);
    println!("{}", cache.get(1));  // 1
    cache.put(3, 3);
    println!("{}", cache.get(2));  // -1
    cache.put(4, 4);
    println!("{}", cache.get(1));  // -1
    println!("{}", cache.get(3));  // 3
    println!("{}", cache.get(4));  // 4
}

package main

import "fmt"

type DLLNode struct {
  key   int
  value int
  prev  *DLLNode
  next  *DLLNode
}

type LRUCache struct {
  capacity int
  cache    map[int]*DLLNode
  head     *DLLNode
  tail     *DLLNode
}

func Constructor(capacity int) LRUCache {
  head := &DLLNode{}
  tail := &DLLNode{}
  head.next = tail
  tail.prev = head

  return LRUCache{
    capacity: capacity,
    cache:    make(map[int]*DLLNode),
    head:     head,
    tail:     tail,
  }
}

func (c *LRUCache) Get(key int) int {
  if node, ok := c.cache[key]; ok {
    c.moveToHead(node)
    return node.value
  }
  return -1
}

func (c *LRUCache) Put(key int, value int) {
  if node, ok := c.cache[key]; ok {
    node.value = value
    c.moveToHead(node)
  } else {
    if len(c.cache) >= c.capacity {
      c.removeTail()
    }
    node := &DLLNode{key: key, value: value}
    c.cache[key] = node
    c.addToHead(node)
  }
}

func (c *LRUCache) moveToHead(node *DLLNode) {
  c.removeNode(node)
  c.addToHead(node)
}

func (c *LRUCache) removeNode(node *DLLNode) {
  node.prev.next = node.next
  node.next.prev = node.prev
}

func (c *LRUCache) addToHead(node *DLLNode) {
  node.next = c.head.next
  node.prev = c.head
  c.head.next.prev = node
  c.head.next = node
}

func (c *LRUCache) removeTail() {
  node := c.tail.prev
  c.removeNode(node)
  delete(c.cache, node.key)
}

func main() {
  cache := Constructor(2)
  cache.Put(1, 1)
  cache.Put(2, 2)
  fmt.Println(cache.Get(1))  // 1
  cache.Put(3, 3)
  fmt.Println(cache.Get(2))  // -1
  cache.Put(4, 4)
  fmt.Println(cache.Get(1))  // -1
  fmt.Println(cache.Get(3))  // 3
  fmt.Println(cache.Get(4))  // 4
}

Approach 2: OrderedDict / LinkedHashMap

🎯 Interview Favourite

Use a language’s built-in ordered hash map (Python’s OrderedDict, Java’s LinkedHashMap, JavaScript’s Map) which maintains insertion order and allows fast key reordering.

This approach achieves the same O(1) time complexity with less code, since the language handles the doubly linked list for you.

⏱ Time O(1) Built-in ordered ops 💾 Space O(capacity) Hash + internal linked list

Step-by-step Example

Same sequence as Approach 1: LRUCache(2) → put(1,1) → put(2,2) → get(1) → put(3,3) → get(2)

With OrderedDict, the order is maintained automatically:

Step	Operation	OrderedDict State	Action
1	`put(1, 1)`	`{1: 1}`	Insert; order is `[1]`
2	`put(2, 2)`	`{1: 1, 2: 2}`	Insert; order is `[1, 2]`
3	`get(1)`	`{1: 1, 2: 2}`	Access 1; move to end: order is `[2, 1]`
4	`put(3, 3)`	`{1: 1, 3: 3}`	Insert 3; pop oldest (2); order is `[1, 3]`
5	`get(2)`	`{1: 1, 3: 3}`	Return -1 (2 not found)

Pseudocode

class LRUCache:
    capacity, cache (OrderedDict)

    get(key):
        if key not in cache:
            return -1
        cache.move_to_end(key)  // Language handles reordering
        return cache[key]

    put(key, value):
        if key in cache:
            cache[key] = value
            cache.move_to_end(key)
        else:
            if cache.size >= capacity:
                cache.popitem(FIFO)  // Remove oldest (first inserted)
            cache[key] = value

Solution Code

from collections import OrderedDict
from typing import Any


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache: OrderedDict[int, int] = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache[key] = value
            self.cache.move_to_end(key)
        else:
            if len(self.cache) >= self.capacity:
                self.cache.popitem(last=False)
            self.cache[key] = value


# Test
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))  # 1
cache.put(3, 3)
print(cache.get(2))  # -1
cache.put(4, 4)
print(cache.get(1))  # -1
print(cache.get(3))  # 3
print(cache.get(4))  # 4

#include <iostream>
#include <map>

class LRUCache {
private:
    int capacity;
    std::map<int, int> cache;
    int timestamp = 0;
    std::map<int, int> access_time;

public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        if (cache.find(key) == cache.end()) {
            return -1;
        }
        access_time[key] = ++timestamp;
        return cache[key];
    }

    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            cache[key] = value;
            access_time[key] = ++timestamp;
        } else {
            if ((int)cache.size() >= capacity) {
                int lru_key = -1;
                int min_time = INT_MAX;
                for (auto& p : access_time) {
                    if (cache.find(p.first) != cache.end() && p.second < min_time) {
                        min_time = p.second;
                        lru_key = p.first;
                    }
                }
                cache.erase(lru_key);
                access_time.erase(lru_key);
            }
            cache[key] = value;
            access_time[key] = ++timestamp;
        }
    }
};

int main() {
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    std::cout << cache.get(1) << std::endl;  // 1
    cache.put(3, 3);
    std::cout << cache.get(2) << std::endl;  // -1
    cache.put(4, 4);
    std::cout << cache.get(1) << std::endl;  // -1
    std::cout << cache.get(3) << std::endl;  // 3
    std::cout << cache.get(4) << std::endl;  // 4
    return 0;
}

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache {
    private int capacity;
    private LinkedHashMap<Integer, Integer> cache;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > capacity;
            }
        };
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        return cache.get(key);
    }

    public void put(int key, int value) {
        cache.put(key, value);
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1));  // 1
        cache.put(3, 3);
        System.out.println(cache.get(2));  // -1
        cache.put(4, 4);
        System.out.println(cache.get(1));  // -1
        System.out.println(cache.get(3));  // 3
        System.out.println(cache.get(4));  // 4
    }
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
    }

    get(key) {
        if (!this.cache.has(key)) {
            return -1;
        }
        const value = this.cache.get(key);
        this.cache.delete(key);
        this.cache.set(key, value);
        return value;
    }

    put(key, value) {
        if (this.cache.has(key)) {
            this.cache.delete(key);
        } else if (this.cache.size >= this.capacity) {
            const oldestKey = this.cache.keys().next().value;
            this.cache.delete(oldestKey);
        }
        this.cache.set(key, value);
    }
}

const cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1));  // 1
cache.put(3, 3);
console.log(cache.get(2));  // -1
cache.put(4, 4);
console.log(cache.get(1));  // -1
console.log(cache.get(3));  // 3
console.log(cache.get(4));  // 4

use std::collections::HashMap;

struct LRUCache {
    capacity: usize,
    cache: HashMap<i32, i32>,
    order: Vec<i32>,
}

impl LRUCache {
    fn new(capacity: i32) -> Self {
        LRUCache {
            capacity: capacity as usize,
            cache: HashMap::new(),
            order: Vec::new(),
        }
    }

    fn get(&mut self, key: i32) -> i32 {
        if let Some(&value) = self.cache.get(&key) {
            if let Some(pos) = self.order.iter().position(|&k| k == key) {
                self.order.remove(pos);
                self.order.push(key);
            }
            value
        } else {
            -1
        }
    }

    fn put(&mut self, key: i32, value: i32) {
        if self.cache.contains_key(&key) {
            self.cache.insert(key, value);
            if let Some(pos) = self.order.iter().position(|&k| k == key) {
                self.order.remove(pos);
            }
            self.order.push(key);
        } else {
            if self.cache.len() >= self.capacity {
                if let Some(lru_key) = self.order.first().copied() {
                    self.cache.remove(&lru_key);
                    self.order.remove(0);
                }
            }
            self.cache.insert(key, value);
            self.order.push(key);
        }
    }
}

fn main() {
    let mut cache = LRUCache::new(2);
    cache.put(1, 1);
    cache.put(2, 2);
    println!("{}", cache.get(1));  // 1
    cache.put(3, 3);
    println!("{}", cache.get(2));  // -1
    cache.put(4, 4);
    println!("{}", cache.get(1));  // -1
    println!("{}", cache.get(3));  // 3
    println!("{}", cache.get(4));  // 4
}

package main

import "fmt"

type LRUCache struct {
  capacity int
  cache    map[int]int
  order    []int
}

func Constructor(capacity int) LRUCache {
  return LRUCache{
    capacity: capacity,
    cache:    make(map[int]int),
    order:    make([]int, 0),
  }
}

func (c *LRUCache) Get(key int) int {
  if value, ok := c.cache[key]; ok {
    c.moveToEnd(key)
    return value
  }
  return -1
}

func (c *LRUCache) Put(key int, value int) {
  if _, ok := c.cache[key]; ok {
    c.cache[key] = value
    c.moveToEnd(key)
  } else {
    if len(c.cache) >= c.capacity {
      lruKey := c.order[0]
      delete(c.cache, lruKey)
      c.order = c.order[1:]
    }
    c.cache[key] = value
    c.order = append(c.order, key)
  }
}

func (c *LRUCache) moveToEnd(key int) {
  for i, k := range c.order {
    if k == key {
      c.order = append(c.order[:i], c.order[i+1:]...)
      c.order = append(c.order, key)
      break
    }
  }
}

func main() {
  cache := Constructor(2)
  cache.Put(1, 1)
  cache.Put(2, 2)
  fmt.Println(cache.Get(1))  // 1
  cache.Put(3, 3)
  fmt.Println(cache.Get(2))  // -1
  cache.Put(4, 4)
  fmt.Println(cache.Get(1))  // -1
  fmt.Println(cache.Get(3))  // 3
  fmt.Println(cache.Get(4))  // 4
}

Common mistakes

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

"""
Solution for LRU Cache
"""

def solve():
    """Implementation for approach 3 of LRU Cache"""
    pass

if __name__ == "__main__":
    print("Solution ready")

#include <bits/stdc++.h>
using namespace std;

// Solution for LRU Cache
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

/**
 * Solution for LRU Cache
 * Approach 3
 */
public class LruCacheSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

/**
 * Solution for LRU Cache
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

/// Solution for LRU Cache
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

package main

import "fmt"

// Solution for LRU Cache
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Interview Tips

Hash Map + DLL vs. OrderedDict: The first demonstrates deep understanding of data structures; the second is more pragmatic and error-resistant.
Why not just a hash map? You lose the ability to evict in constant time without tracking access order.
Why not just a list? Searching for a key is O(n). A hash map is essential for O(1) lookups.
Edge cases to mention:
- Capacity = 1 (every new key evicts the only item).
- Repeated accesses to the same key (should not allocate new space).
- Updating an existing key’s value (should not evict anything).
- Reaching exactly capacity before the next insertion.
Follow-up — LFU Cache (#460): Instead of “least recently used,” track “least frequently used” — requires a more complex data structure with frequency counters.

LRU Cache

Problem Statement

Examples

Constraints

Real-World Applications

Complexity Comparison

Which approach should you learn first?

Approach 1: Hash Map + Doubly Linked List (Recommended)

Step-by-step Example

Pseudocode

Solution Code

Approach 2: OrderedDict / LinkedHashMap

Step-by-step Example

Pseudocode

Solution Code

Common mistakes

Approach 3: Space-Optimized Variant

Pseudocode

Solution Code

Related Problems

Interview Tips