LFU Cache

Hard Design Data Structures Linked Lists Original on LeetCode

LFU Cache is a hard design data structures problem solved with the linked lists pattern. The best approach, optimal (count buckets + minimum count), runs in O(1) average per operation time and O(capacity) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan for the victim) up.

Problem

Build a class LFUCache that stores key–value pairs and can hold at most capacity of them. LFUCache(int capacity) creates an empty cache.

get(int key) returns the value stored for key, or -1 if it is absent. put(int key, int value) stores the value, overwriting it if the key is already present. Every successful get and every put counts as one use of that key; a key that has just been inserted has been used once.

When a put brings a new key into a cache that is already full, the cache first evicts the key with the fewest uses. If several keys tie, it evicts the one among them whose last use is the oldest. Both operations must run in O(1) average time.

Examples

Example 1

Input
LFUCache(2), put(5, 50), put(8, 80), get(5), put(3, 30), get(8), get(3), get(5)
Output
50, -1, 30, 50
Why
After get(5), key 5 has been used twice and key 8 once, so adding key 3 to the full cache evicts key 8.

Example 2

Input
LFUCache(2), put(1, 10), put(2, 20), get(1), get(2), put(4, 40), get(1), get(2), get(4)
Output
10, 20, -1, 20, 40
Why
Keys 1 and 2 are both used twice; key 1 was touched longer ago, so the tie is broken by evicting it.

Example 3

Input
LFUCache(1), put(6, 1), put(6, 2), get(6), put(7, 3), get(6), get(7)
Output
2, -1, 3
Why
Overwriting key 6 counts as a use but frees no space; with room for one entry, key 7 pushes key 6 out.

Constraints

  • 1 <= capacity <= 10^4
  • 0 <= key <= 10^5
  • 0 <= value <= 10^9
  • At most 2 * 10^5 calls to get and put in total.
  • Both get and put must run in O(1) average time.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (scan for the victim)O(capacity) per put that evicts, O(1) otherwiseO(capacity)
Optimal (count buckets + minimum count)O(1) average per operationO(capacity)

1Brute force (scan for the victim)

TimeO(capacity) per put that evicts, O(1) otherwiseChoosing a victim looks at every stored entry.
SpaceO(capacity)Each of at most `capacity` keys stores three numbers.

Store each key with its value, its use count and the tick of its last use. Lookups are direct, but when the cache is full you scan every entry and pick the one with the smallest count, breaking ties by the oldest tick.

  1. Keep a global counter tick that grows on every access.
  2. get(key): if missing return -1; otherwise add 1 to its count, set its last use to the next tick and return the value.
  3. put(key, value) on an existing key: update the value, add 1 to the count and refresh the tick.
  4. put on a new key when full: scan all entries for the smallest (count, lastUse) pair and remove that key.
  5. Insert the new key with count 1 and the next tick.
class LFUCache {
    private final int capacity;
    private final Map<Integer, int[]> data = new HashMap<>(); // key -> {value, count, lastUse}
    private int tick = 0;

    public LFUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        int[] e = data.get(key);
        if (e == null) return -1;
        e[1]++;
        e[2] = ++tick;
        return e[0];
    }

    public void put(int key, int value) {
        int[] e = data.get(key);
        if (e != null) {
            e[0] = value;
            e[1]++;
            e[2] = ++tick;
            return;
        }
        if (data.size() == capacity) {
            int victim = -1;
            int[] best = null;
            for (Map.Entry<Integer, int[]> en : data.entrySet()) {
                int[] v = en.getValue();
                if (best == null || v[1] < best[1] || (v[1] == best[1] && v[2] < best[2])) {
                    best = v;
                    victim = en.getKey();
                }
            }
            data.remove(victim);
        }
        data.put(key, new int[] { value, 1, ++tick });
    }
}

2Optimal (count buckets + minimum count)

TimeO(1) average per operationEvery step is a hash lookup or an insertion/removal in an insertion-ordered hash set.
SpaceO(capacity)Each stored key appears once in the maps and once in one bucket.

Put every key into a bucket for its use count. Each bucket is an insertion-ordered set, so its first key is the least recently used one with that count. Track minCount, the smallest count that has a non-empty bucket: the victim is always the first key of bucket minCount. Touching a key moves it from bucket c to the end of bucket c + 1, and only that move can raise minCount, by exactly one.

  1. Keep vals (key -> value), counts (key -> count), buckets (count -> ordered set of keys) and minCount.
  2. touch(key): remove it from bucket c; if that bucket was minCount and is now empty, raise minCount to c + 1; append the key to bucket c + 1.
  3. get(key): missing -> -1; otherwise touch it and return its value.
  4. put on an existing key: update the value and touch it.
  5. put on a new key: if full, remove the first key of bucket minCount from everything; then store the key with count 1, append it to bucket 1 and set minCount to 1.
class LFUCache {
    private final int capacity;
    private final Map<Integer, Integer> vals = new HashMap<>();
    private final Map<Integer, Integer> counts = new HashMap<>();
    private final Map<Integer, LinkedHashSet<Integer>> buckets = new HashMap<>();
    private int minCount = 0;

    public LFUCache(int capacity) {
        this.capacity = capacity;
    }

    private void touch(int key) {
        int c = counts.get(key);
        LinkedHashSet<Integer> b = buckets.get(c);
        b.remove(key);
        if (b.isEmpty()) {
            buckets.remove(c);
            if (minCount == c) minCount = c + 1;
        }
        counts.put(key, c + 1);
        buckets.computeIfAbsent(c + 1, x -> new LinkedHashSet<>()).add(key);
    }

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

    public void put(int key, int value) {
        if (vals.containsKey(key)) {
            vals.put(key, value);
            touch(key);
            return;
        }
        if (vals.size() == capacity) {
            LinkedHashSet<Integer> b = buckets.get(minCount);
            int victim = b.iterator().next();
            b.remove(victim);
            if (b.isEmpty()) buckets.remove(minCount);
            vals.remove(victim);
            counts.remove(victim);
        }
        vals.put(key, value);
        counts.put(key, 1);
        buckets.computeIfAbsent(1, x -> new LinkedHashSet<>()).add(key);
        minCount = 1;
    }
}

Edge cases to test

  • Capacity 1: every new key evicts the only entry, whatever its count
  • Several keys share the lowest use count: the least recently used of them goes
  • put on an existing key updates the value and raises its count, but never evicts
  • A newly inserted key starts with count 1, so it is usually the next one evicted
  • get on a missing key returns -1 and changes nothing

Hints

Hint 1

Each key needs a use count. When you must evict, you want the smallest count, and among those the oldest. What tells you the oldest quickly?

Hint 2

Group keys by their count. Inside one group, keep them in the order they were last touched, like a small LRU list.

Hint 3

Keep a map key -> (value, count), a map count -> ordered set of keys, and the current minimum count. A new key always resets the minimum to 1; a touched key only raises the minimum when it leaves the minimum group and that group becomes empty.

FAQ

What is the best time complexity for LFU Cache?

Optimal (count buckets + minimum count) runs in O(1) average per operation time and O(capacity) extra space. Every step is a hash lookup or an insertion/removal in an insertion-ordered hash set.

Which pattern does LFU Cache use?

It is a design data structures problem that uses the linked lists pattern. Other problems with the same pattern: Design Linked List, Design Front Middle Back Queue, LRU Cache.

Is there a brute force solution for LFU Cache?

Yes. Brute force (scan for the victim) takes O(capacity) per put that evicts, O(1) otherwise time and O(capacity) space. Store each key with its value, its use count and the tick of its last use.

Which edge cases should I test for LFU Cache?

Capacity 1: every new key evicts the only entry, whatever its count; Several keys share the lowest use count: the least recently used of them goes; put on an existing key updates the value and raises its count, but never evicts; A newly inserted key starts with count 1, so it is usually the next one evicted; get on a missing key returns -1 and changes nothing.