LFU Cache

What is LFU cache?

LFU (Least Frequently Used) Cache is a type of caching algorithm where the items that have been used least frequently are removed first when the cache reaches its limit.

How to implement it?

A basic LFU Cache requires the following data structures:

• A Hash Map to store key-value pairs in the cache.
• A linked list to maintain the frequency of each item.
• A Hash Map to store ref to the linked list node for each key.

Implementation in Kotlin

package leetcode.datastructures
 
class LFUCache(private val capacity: Int) {
    class Node(val key: Int, var value: Int) {
        var frequency: Int = 1
        var prev: Node? = null
        var next: Node? = null
    }
 
    class DoublyLinkedList {
        var head = Node(0, 0)
        var tail = Node(0, 0)
 
        init {
            tail.prev = head
            head.next = tail
        }
 
        fun addNode(node: Node) {
            node.next = tail
            node.prev = tail.prev
            tail.prev?.next = node
            tail.prev = node
        }
 
        fun removeNode(node: Node) {
            node.prev?.next = node.next
            node.next?.prev = node.prev
        }
    }
 
    private val cache = mutableMapOf<Int, Node>()
    private val frequencyMap = mutableMapOf<Int, DoublyLinkedList>()
    private var minFrequency = 0
 
    fun get(key: Int): Int {
        if (!cache.containsKey(key)) return -1
 
        val node = cache[key]!!
        update(node)
 
        return node.value
    }
 
    fun put(key: Int, value: Int) {
        if (capacity <= 0) return
 
        if (cache.containsKey(key)) {
            val node = cache[key]!!
            node.value = value
            update(node)
            return
        } else {
            if (cache.size == capacity) {
                val node = frequencyMap[minFrequency]!!.head.next!!
                frequencyMap[minFrequency]!!.removeNode(node)
                cache.remove(node.key)
            }
            val newNode = Node(key, value)
            cache[key] = newNode
            if (!frequencyMap.containsKey(newNode.frequency)) {
                frequencyMap[newNode.frequency] = DoublyLinkedList()
            }
            frequencyMap[newNode.frequency]!!.addNode(newNode)
            minFrequency = 1
        }
    }
 
    private fun update(node: Node) {
        val frequency = node.frequency
        node.frequency++
        val keys = frequencyMap[frequency]!!
        keys.removeNode(node)
        if (minFrequency == frequency && keys.head.next == keys.tail) {
            minFrequency++
        }
        if (!frequencyMap.containsKey(frequency + 1)) {
            frequencyMap[frequency + 1] = DoublyLinkedList()
        }
        frequencyMap[frequency + 1]!!.addNode(node)
    }
}

Complexity Analysis

• put - O(1)
• get - O(1)

Space complexity: O(n)