LFU Cache

Free with account Updated Nov 19, 2026 · 8 min read
On this page

    Problem statement

    Design a cache with a fixed capacity that supports get(key) and put(key, value) in O(1) average time. get returns the value or −1. put inserts or updates a key. When the cache is full and a new key arrives, evict the key that has been used the fewest times; if several keys tie, evict the one whose last use is oldest. Both get and put on an existing key count as a use; a newly inserted key has a use count of 1.

    LFU is the harder sibling of LRU Cache, and it is usually asked right after it. LRU needs one ordering (recency); LFU needs two (count, then recency), and the trick is keeping both in O(1) without a heap. Original problem: LeetCode 460.

    Example

    Key 2 is evicted first because it was used once. Later keys 1 and 3 are both at two uses, and key 1's last use is older, so it goes.
    Key 2 is evicted first because it was used once. Later keys 1 and 3 are both at two uses, and key 1's last use is older, so it goes.
    LFUCache(2)
    put(1, A); put(2, B)
    get(1)     -> A        # counts: 1:2, 2:1
    put(3, C)              # evicts 2 (count 1)
    get(2)     -> -1
    get(3)     -> C        # counts: 1:2, 3:2
    put(4, D)              # tie at count 2: key 1 was used longer ago -> evict 1
    get(1)     -> -1
    get(3)     -> C
    get(4)     -> D

    Constraints (assumed)

    • 0 ≤ capacity ≤ 10⁴; up to 2 × 10⁵ calls.
    • Keys and values are integers (letters above for readability).

    What this question tests

    • Breaking a two-level ordering (count, then recency) into structures that each give O(1) updates.
    • Realising that counts only ever go up by one, so you never need a heap to find the new minimum.
    • Keeping three structures consistent on every path: hit, update, insert, evict.

    Questions to ask first

    1. How are ties broken? (Here: least recently used among the lowest count.)
    2. Does put on an existing key count as a use? (Here: yes.)
    3. What count does a new key start with, and does the count survive eviction? (Here: 1; an evicted key starts again at 1.)
    4. Can capacity be 0? (Here: yes; every put is ignored.)