Leetcode

This problem is considered a Medium difficulty level.

Why we need Smart Caching

Speed is the most important thing in the world of high-performance computing. Modern apps, like dynamic websites and complex databases, need quick access to data to give users a good experience. However, getting data from primary storage, like a hard drive or a remote database, can be slow and costly. This is where caching comes in. A cache is a smaller, faster layer of memory that keeps temporary copies of data that is often accessed. It acts as a high-speed buffer between the application and the slower main data source. When systems serve requests from the cache, they can greatly lower latency and make things run more smoothly.

Caches are made to have a limited amount of space. This basic limitation creates a big problem: when the cache is full and a new piece of data needs to be stored, which item should be removed? A “cache eviction policy” controls this choice. First-In-First-Out (FIFO) is a simple policy that says to throw away the oldest item. The Least Recently Used (LRU) policy, on the other hand, is a smarter way to do things. LRU works on the idea of temporal locality, which means that data that was accessed recently is very likely to be accessed again soon. So, when space is needed, an LRU cache gets rid of the item that hasn’t been used in the longest time.

The LeetCode problem #146, LRU Cache, is a classic computer science problem that asks programmers to make and use this data structure. This challenge goes beyond just schoolwork; it’s a small-scale version of real-world system design that requires careful balancing of conflicting needs like instant access, quick updates, efficient eviction, and fixed memory usage. The main issue is meeting these needs while keeping performance in mind, which is a great way to test a developer’s knowledge of data structures and their trade-offs.

Deconstructing the Challenge: The LRU Cache Problem

The problem statement for LeetCode 146 is precise and demanding. It requires the implementation of a data structure that adheres to the constraints of a Least Recently Used cache. The implementation must expose a specific public interface:

• LRUCache(int capacity): This constructor initialises the cache with a fixed, positive size. The capacity defines the maximum number of key-value pairs the cache can hold at any given time.
• int get(int key): This function should return the value associated with the given key. If the key exists in the cache, its value is returned. Crucially, this access must mark the key as having been “recently used.” If the key does not exist, the function must return -1.
• void put(int key, int value): This function is responsible for either inserting a new key-value pair or updating an existing one. If it key already exists, it value is updated. If it key is new, the key-value pair is added to the cache. In either case, this operation also marks the key as “recently used”. If adding a new key causes the number of items to exceed the cache’s capacity, the least recently used key must be evicted before the new item is inserted.

The most critical requirement, which dictates the entire design of the solution, is the performance constraint: “The functions get putmust each run in O(1) average time complexity.” This means that no matter how large the cache’s capacity is, the time taken to retrieve or insert an item should remain constant on average.

To make these rules tangible, consider the following step-by-step walkthrough of the example provided in the problem description, using a cache with a capacity of 2.

| Operation   | Action                                                 | Cache State (MRU -> LRU) | Output |
| :---------- | :----------------------------------------------------- | :----------------------- | :----- |
| `put(1, 1)` | Add {1:1}. Cache size is 1.                            | `{1:1}`                  | `null` |
| `put(2, 2)` | Add {2:2}. Cache size is 2.                            | `{2:2}, {1:1}`           | `null` |
| `get(1)`    | Access {1:1}. It becomes the most recently used (MRU). | `{1:1}, {2:2}`           | `1`    |
| `put(3, 3)` | Cache is full. Evict LRU item {2:2}. Add {3:3} as MRU. | `{3:3}, {1:1}`           | `null` |
| `get(2)`    | Key 2 was evicted and is no longer in the cache.       | `{3:3}, {1:1}`           | `-1`   |
| `put(4, 4)` | Cache is full. Evict LRU item {1:1}. Add {4:4} as MRU. | `{4:4}, {3:3}`           | `null` |

The Quest for O(1): Why Simple Data Structures Fall Short

The stringent O(1) time complexity requirement for both get and put operations immediately disqualifies several intuitive but ultimately inefficient approaches. A careful analysis of common data structures reveals that none, in isolation, can satisfy all the problem’s constraints.

Approach 1: Using an Array or List

A simple array or list could maintain the order of items, with the most recently used item at one end and the least recently used at the other. However, this approach fails on multiple fronts. To perform an operation,get(key) one would need to scan the list to find the item with the matching key, an operation that takes linear time, or O(n), where n is the number of items in the cache. Similarly, after a successful move,get moving the accessed item from its current position to the front of the list would require shifting all preceding elements, which is also an O(n) operation.

Approach 2: Using a Hash Map Alone

A hash map (or dictionary) is the go-to data structure for O(1) average-time lookups, insertions, and deletions. It seems like a promising candidate because it can satisfy the fast access requirement of the get and put methods. However, a standard hash map provides no guarantees about the order of its elements. When the cache is full and an eviction is necessary, there is no efficient way to identify the “least recently used” item. Determining the LRU item would require iterating over all key-value pairs in the map, perhaps comparing timestamps stored alongside the values, which degrades performance to O(n).

Approach 3: Using a Singly Linked List

A singly linked list improves upon an array for reordering, as adding a new node to the head of the list is an O(1) operation. However, it still suffers from major drawbacks. First, finding a node by its key requires traversing the list from the head, an O(n) process. Second, and more critically, evicting the LRU item   which would be at the tail of the list   is inefficient. To remove the tail node in a singly linked list, one must first traverse to the second-to-last node to update its next pointer, which again takes O(n) time.

The analysis of these simple structures leads to a crucial realisation: the problem’s requirements are fundamentally in conflict when viewed through the lens of a single data structure. We need the rapid, key-based lookup capability of a hash map and the dynamic, ordered nature of a linked list. No structure alone possesses both properties. The solution, therefore, cannot be to choose one over the other but to compose them into a hybrid data structure that leverages the strengths of both.

The Optimal Blueprint: The Hash Map and Doubly Linked List Synergy

The canonical and most efficient solution to the LRU Cache problem is a powerful combination of two data structures: a hash map and a doubly linked list. This composite structure elegantly resolves the conflicting requirements by assigning each component a specific role, allowing them to work in synergy to achieve the desired O(1) performance for all operations.

The Hash Map’s Role: O(1) Lookups

The hash map serves as the primary index for the cache. Its purpose is to provide immediate, O(1) average-time access to any item in the cache given its key. However, instead of storing the item’s value directly, the hash map will store a reference (or pointer) to the corresponding node within the doubly linked list. This mapping, from key to Node, is the critical link that bridges the gap between fast, unordered lookups and the ordered list. When an operation like get(key) is called, the hash map is used to instantly locate the relevant node in the list without any traversal.

The Doubly Linked List’s Role: O(1) Reordering and Eviction

The doubly linked list is responsible for maintaining the recency order of all items in the cache. The list is organised such that the most recently used (MRU) item is always at the head and the least recently used (LRU) item is always at the tail.

The choice of a doubly linked list is deliberate and essential. Each node in a doubly linked list contains pointers to both the next and the prev nodes in the sequence. This bidirectional linking is what enables O(1) reordering. Once the hash map provides a direct reference to a node, that node can be removed from its current position and moved to the head of the list in constant time. This is because we can directly access its neighbors (node.prev and node.next) and “patch” the list by connecting them to each other, all without any traversal. Similarly, when an eviction is required, the LRU node at the tail of the list can be removed in O(1) time because its predecessor is immediately known via the tail.prev pointer.

To further simplify the implementation and eliminate edge cases (such as an empty list or a list with a single element), a common technique is to use two dummy nodes: a head a tail sentinel. These sentinels do not store any actual cache data but serve as fixed boundaries.

All real cache nodes are inserted between head and tail. This ensures that any node being added or removed always has non-null neighbours, streamlining the pointer manipulation logic.

This design creates two distinct but perfectly synchronised views of the same data. The hash map provides an unordered, key-based view for fast access, while the linked list provides an ordered, recency-based view for fast eviction and reordering. The integrity of the cache depends on every operation atomically updating both views to maintain consistency.

Algorithm in Action: A Step-by-Step Walkthrough

With the dual-structure blueprint established, the logic for the get and putmethods becomes a clear sequence of operations that manipulate both the hash map and the doubly linked list in concert.

The get(key) Algorithm

The get operation is a read request from the user’s perspective, but it triggers an internal state change by updating the accessed item’s recency.

1. Lookup in Hash Map:

• Check if it key exists as a key in the hashMap

2. Handle Cache Miss:

• If the key is not found, the item is not in the cache. Return -1.

3. Handle Cache Hit: If the key is found:

• Retrieve the reference to the corresponding node from the hashMap.
• Move this node to the head of the doublyLinkedList. This action marks it as the most recently used item. This job is typically done by a helper function that first unlinks the node from its current position and then re-inserts it at the head.
• Return the value stored within the node.

The put(key, value) Algorithm

The put operation handles both the creation of new items and the update of existing ones. Its logic must branch to manage these two scenarios correctly and handle potential eviction.

1. Lookup in Hash Map: Check if it key already exists in the hashMap.
2. Handle Existing Key (Update): If the key is found:

3. Retrieve the reference to the existing node from the hashMap.

4. Update the value of this node with the new value provided.

5. Move this node to the head of the doublyLinkedList to mark it as the most recently used.

6. Handle New Key (Insert): If the key is not found:

7. Create a new one node containing the specified key and value.

8. Add this new one node to the head of the doublyLinkedList.

9. Add a new entry to the hashMap, mapping the key to the newly created node.

10. Check for Capacity Overflow: After adding the new node, check if the size of the cache now exceeds its capacity.

11. Perform Eviction: If the cache is over capacity:

• Identify the LRU node, which is the node at the tail doublyLinkedList (specifically, the node just before the dummy tail sentinel).
• Remove this LRU node’s key from the hashMap.
• Remove the LRU node itself from the doublyLinkedList.

This algorithmic design ensures that every operation maintains the invariant: the hash map always contains keys present in the cache, and the linked list always reflects their use order from most to least recent.

Implementation in Kotlin (Part 1): Building from First Principles

For technical interviews and a foundational understanding, it is crucial to be able to implement the LRU Cache from scratch. The following Kotlin code demonstrates how to build the structure using a custom Node class, a for loop forMutableMap the hash map, and dummy head/tail nodes for the doubly linked list.

The use of non-nullable dummy head and tailnodes is a key implementation detail. It dramatically simplifies the pointer logic by transforming all insertion and removal operations into the “general case” of manipulating a node between two existing neighbours, thereby eliminating the need for special checks for edge cases, like an empty list.

Kotlin

class LRUCache(private val capacity: Int) {
    // Inner class to represent a node in the doubly linked list
    private class Node(
        var key: Int,
        var value: Int,
        var prev: Node? = null,
        var next: Node? = null
    )
    // The cache map for O(1) key-to-node lookup
    private val cache: MutableMap<Int, Node> = HashMap()
    
    // Dummy head and tail nodes to simplify list manipulation
    private val head: Node = Node(-1, -1)
    private val tail: Node = Node(-1, -1)
    init {
        // Initialize the doubly linked list with dummy nodes
        head.next = tail
        tail.prev = head
    }
    // Helper function to remove a node from the list
    private fun removeNode(node: Node) {
        val prevNode = node.prev
        val nextNode = node.next
        prevNode?.next = nextNode
        nextNode?.prev = prevNode
    }
    // Helper function to add a node to the head of the list (MRU position)
    private fun addToHead(node: Node) {
        node.prev = head
        node.next = head.next
        head.next?.prev = node
        head.next = node
    }
    fun get(key: Int): Int {
        val node = cache[key]
        if (node == null) {
            // Key not found in cache
            return -1
        } else {
            // Key found, move the node to the head to mark it as most recently used
            removeNode(node)
            addToHead(node)
            return node.value
        }
    }
    fun put(key: Int, value: Int) {
        val node = cache[key]
        if (node!= null) {
            // Key already exists, update its value and move it to the head
            node.value = value
            removeNode(node)
            addToHead(node)
        } else {
            // Key does not exist, create a new node
            val newNode = Node(key, value)
            cache[key] = newNode
            addToHead(newNode)
            // If adding the new node exceeds capacity, evict the LRU item
            if (cache.size > capacity) {
                val lruNode = tail.prev
                if (lruNode!= null) {
                    removeNode(lruNode)
                    cache.remove(lruNode.key)
                }
            }
        }
    }
}

Implementation in Kotlin (Part 2): The LinkedHashMap Shortcut

While building data structures from scratch is an excellent exercise, effective software engineering often involves leveraging well-tested components from a language’s standard library. For implementing an LRU Cache, Kotlin (via the Java standard library) provides a powerful and concise tool LinkedHashMap

A LinkedHashMap is a special map implementation that maintains a doubly linked list running through all of its entries. By default, this list maintains insertion order. However, it has a special constructor that allows it to maintain an access order.

When constructed with the accessOrder parameter set to anytrue time an entry is accessed via getthe end of the internal linked list. This behaviour perfectly mirrors the recency update required by an LRU cache.

To enforce the capacity constraint, one can subclass LinkedHashMap and override a single protected method.removeEldestEntry() This method is called by the map after a new element is inserted, and if it returns true, the “eldest” entry (the least recently accessed item in access-order mode) is automatically removed. This provides a clean, declarative way to manage eviction.

The resulting code is remarkably elegant and robust, abstracting away all the manual pointer manipulation.

Kotlin

import java.util.LinkedHashMap

class LRUCacheWithLinkedHashMap(private val capacity: Int) : 
    LinkedHashMap<Int, Int>(capacity, 0.75f, true) {

    /**
     * This method is invoked by put and putAll after inserting a new entry into the map.
     * It provides the implementor with the opportunity to remove the eldest entry each time
     * a new one is added. This is ideal for implementing a cache with a fixed capacity.
     *
     * @param eldest The least recently accessed entry in the map.
     * @return true if the eldest entry should be removed, false otherwise.
     */
    override fun removeEldestEntry(eldest: MutableMap.MutableEntry<Int, Int>?): Boolean {
        return size > capacity
    }
}

// The get and put methods are inherited from LinkedHashMap and work as required.
// No additional implementation is needed for the core LRU logic.

This LinkedHashMap solution demonstrates the power of abstraction. While understanding the underlying mechanics (as shown in the manual implementation) is vital, knowing when to use a pre-built, optimized tool is the hallmark of a productive engineer.

Final Analysis: Time and Space Complexity

The performance of the optimal solution, whether implemented manually or with LinkedHashMap, is identical and meets the problem’s strict requirements.

Time Complexity: O(1)

• get(key): This operation consists of a hash map lookup and a constant number of pointer manipulations in the linked list. A hash map lookup takes O(1) on average. The list operations (unlinking and re-linking a node) involve updating a fixed number of pointers, which is also an O(1) operation. Therefore, the total average time complexity for get is O(1).
• put(key, value): This operation involves a hash map lookup/insertion (average O(1)), potentially creating a new node (O(1)), and performing a constant number of pointer manipulations to add a node to the head and, if necessary, remove a node from the tail. All of these are constant-time operations. Thus, the total average time complexity for put is also O(1).

It is important to note the nuances of “average time complexity.” This phrasing acknowledges that in the worst-case scenario of catastrophic hash collisions, hash map operations can degrade to O(n). However, with a well-designed hashing function, this is exceedingly rare in practice, and the performance is considered amortised constant time.

Space Complexity: O(capacity)

The space required by the data structure is directly proportional to the maximum number of items it can store.

• The hash map stores capacity key-to-node references.
• The doubly linked list stores up to capacity nodes. Since both structures scale linearly with the capacity, the overall space complexity is O(capacity).

Beyond the Interview

The LRU Cache problem is a cornerstone of technical interviews for a valid reason. It tests not just knowledge of individual data structures but also the ability to analyse a complex set of requirements and synthesise a novel solution by composing simpler components. The process of rejecting naive approaches and arriving at the elegant hash map and doubly linked list pattern is an exemplary lesson in algorithmic design and trade-off analysis.

The pattern itself   using a hash map for fast lookups and a linked list to maintain a dynamic order   is a powerful and widely applicable technique. It appears in various real-world systems, including operating system page replacement algorithms, database buffer pools, and web browser caches.

Furthermore, understanding the LRU Cache provides a solid foundation for tackling more advanced caching strategies, such as the Least Frequently Used (LFU) cache, which introduces the additional complexity of tracking access frequencies. Ultimately, mastering problems like LeetCode 146 is about more than memorising a solution; it is about cultivating a deep intuition for how data structures can be combined to build efficient, high-performance systems. This skill is indispensable for any software engineer aiming to create robust and scalable applications.

Sources:

• https://www.davthecoder.com/blog/how-to-solve-146-leetcode-lru-cache-in-kotlin
• https://leetcode.com/problems/lru-cache
• https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU
• https://www.bigocheatsheet.com/