DEV Community

AussieCoder
AussieCoder

Posted on

LeetCode Solution: 146. LRU Cache

#leetcode #dsa #programming #tutorial

LRU Cache: Because Your Computer Has Commitment Issues (LeetCode 146)

Hello, fellow coders and aspiring digital hoarders! Today, we're diving into a LeetCode classic that’s as common in interviews as "tell me about yourself" – the LRU Cache. If you've ever wondered how your web browser remembers your favorite sites, or why some app data seems to magically stay while older stuff vanishes, you're about to find out!

The Problem: Your Computer's Short-Term Memory

Imagine you have a super-important, but very small, desk. You can only fit a capacity number of items on it. When you put a new item on the desk:

  1. If the item is already there, you just update its content and put it on top (making it shiny and new).
  2. If it's new, you add it to the desk.
  3. Crucially: If adding this new item means your desk is now overflowing, you must throw away the item you haven't touched in the longest time. We call this the "Least Recently Used" (LRU) item. Out with the old, in with the slightly less old, maybe!

When you get an item from the desk:

  1. If it's there, great! You pick it up, use it, and then put it back on top of the desk (making it the most recently used).
  2. If it's not there, well, that's just awkward. You return -1.

The catch? Both get and put operations must be ridiculously fast, specifically O(1) on average. Because nobody has time for slow memory.

Intuition: The "Aha!" Moment 💡

At first glance, this problem might seem like a digital version of "Simon Says" with extra steps. You need to:

  1. Find things fast: If you have key 10, you need to grab its value immediately. A plain list would mean searching through everything, which is O(N) – no good for our O(1) requirement. This screams Hash Map! A map (or unordered_map in C++) lets us look up a key and get its value in average O(1) time.

  2. Maintain order and recency: How do we know what's LRU or MRU? A simple array won't work, because moving items around in an array (to make something MRU) is also O(N). We need something where we can easily remove an item from the middle and add it to the end (or beginning) in O(1) time. This, my friends, is the job for a Doubly Linked List! With prev and next pointers, a node can be unlinked and relinked with constant pointer manipulations.

So, the "aha!" moment is realizing we need both of them. The Hash Map gives us O(1) access to any item by its key, and crucially, it will store a pointer to that item's location in our Doubly Linked List. The Doubly Linked List then maintains the usage order, making it trivial to identify the LRU item (the one at the tail) and move an item to the MRU position (the head).

Approach: The Dynamic Duo Strikes Back!

Our strategy is simple yet elegant, like a perfectly optimized pantry:

  1. The Dynamic Duo:

    • We'll use a std::unordered_map<int, ListNode*> (let's call it cacheMap) to map each key to its corresponding ListNode in our linked list. This gives us lightning-fast lookups (key -> node).
    • We'll use a Doubly Linked List to keep track of the access order. The head of our list will always point to the Most Recently Used (MRU) item, and the tail will point to the Least Recently Used (LRU) item. To simplify things, we'll use "dummy" head and tail nodes that don't store actual data. They just act as bookends, making insertions and deletions much cleaner.

  2. The ListNode Structure:
    Each node in our doubly linked list will be a struct ListNode containing:

    • key: The actual key stored.
    • value: The value associated with the key.
    • prev: A pointer to the previous node.
    • next: A pointer to the next node.

  3. Core Operations (deleteNode, insertNode):
    These are our utility belt items, doing the heavy lifting in O(1):

    • deleteNode(node): Takes a node and removes it from its current position in the linked list by updating its neighbors' prev and next pointers. Poof, gone!
    • insertNode(node): Takes a node and inserts it right after our dummy head node. This effectively makes it the new MRU item. "Welcome to the front row!"

  4. LRUCache(int capacity):

    • Initialize our cacheMap.
    • Create our dummy head and tail nodes.
    • Link head->next = tail and tail->prev = head. An empty list, ready for action!

  5. int get(int key):

    • "Is this key even VIP enough to be in our exclusive club?" Check cacheMap.
    • If key isn't found (cacheMap.find(key) == cacheMap.end()), return -1. "Nope, not found. Try harder next time!"
    • If found:
      • Retrieve the ListNode* using cacheMap[key].
      • "Found it! Now it's super popular, so move it to the front." Call deleteNode() on it to remove it from its old spot.
      • Call insertNode() on it to place it right after the head.
      • Return the node->value.

  6. void put(int key, int value):

    • "Does this key already have a reservation?" Check cacheMap.
    • If key is found:
      • Retrieve the ListNode* from cacheMap.
      • Update its value.
      • "Ah, you're back! Let's update your info and put you at the top." deleteNode() and insertNode() to refresh its MRU status.
    • If key is not found:
      • "New face! Welcome to the party. Let's add you." Create a new ListNode(key, value).
      • Add it to cacheMap: cacheMap[key] = newNode;.
      • insertNode(newNode) to make it MRU.
      • "Party's getting a bit crowded, isn't it?" Check if (cacheMap.size() > capacity):
        • "Time for some tough decisions. Who's the least social butterfly?" The LRU node is always tail->prev.
        • "Sorry, old friend, your time has come."
        • deleteNode(tail->prev) to remove it from the list.
        • cacheMap.erase(tail->prev->key) to remove it from the map.
        • delete tail->prev; to free up that memory (we're not running a charity!).

Code: The Grand Symphony of Pointers and Maps 

#include <unordered_map> // For O(1) average time complexity lookup

// A simple structure for our doubly linked list nodes
struct ListNode {
    int key;
    int value; // Storing the value associated with the key
    ListNode *prev;
    ListNode *next;

    // Constructor: key, value, optional prev/next for convenience
    ListNode(int k, int v, ListNode* p = nullptr, ListNode* n = nullptr) 
        : key(k), value(v), prev(p), next(n) {}
};

class LRUCache {
private:
    std::unordered_map<int, ListNode*> cacheMap; // Maps key to its node in the list
    int capacity; // Maximum number of items the cache can hold
    ListNode *head; // Dummy head node for the doubly linked list
    ListNode *tail; // Dummy tail node for the doubly linked list

    // Helper to remove a node from its current position in the list
    void deleteNode(ListNode* node) {
        // "Hasta la vista, baby!" - The node bids adieu to its neighbors.
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    // Helper to insert a node right after the head (making it the Most Recently Used)
    void insertNode(ListNode* node) {
        // "Making a grand entrance!" - The node proudly claims its spot at the front.
        node->next = head->next;
        node->prev = head;
        head->next->prev = node;
        head->next = node;
    }

public:
    LRUCache(int cap) {
        capacity = cap;
        // Initialize dummy head and tail nodes. Their key/value don't matter.
        // They simplify logic by always having valid 'prev'/'next' for real nodes.
        head = new ListNode(0, 0); 
        tail = new ListNode(0, 0);

        // Link the dummy nodes to each other initially
        head->next = tail;
        tail->prev = head;
    }

    // Destructor to prevent memory leaks, a good practice for C++
    // We allocated nodes with 'new', so we must 'delete' them.
    ~LRUCache() {
        ListNode* current = head;
        while (current != nullptr) {
            ListNode* next = current->next;
            delete current;
            current = next;
        }
    }

    int get(int key) {
        // "Is this key even VIP enough to be in our exclusive club?"
        if (cacheMap.find(key) == cacheMap.end()) {
            return -1; // "Nope, not found. Try harder next time!"
        }

        // Found it! Now it's the coolest kid on the block, move it to the front.
        ListNode* node = cacheMap[key];
        deleteNode(node);
        insertNode(node);
        return node->value; // Return the value, as requested.
    }

    void put(int key, int value) {
        // "Does this key already have a reservation?"
        if (cacheMap.find(key) != cacheMap.end()) {
            // "Ah, you're back! Let's update your info and put you at the top."
            ListNode* node = cacheMap[key];
            node->value = value; // Update the value
            deleteNode(node);
            insertNode(node);
        } else {
            // "New face! Welcome to the party. Let's add you."
            ListNode* newNode = new ListNode(key, value);
            cacheMap[key] = newNode;
            insertNode(newNode);

            // "Party's getting a bit crowded, isn't it?"
            if (cacheMap.size() > capacity) {
                // "Time for some tough decisions. Who's the least social butterfly?"
                // The LRU node is always the one just before the dummy tail.
                ListNode* lruNode = tail->prev;

                // "Sorry, old friend, your time has come." Evict!
                deleteNode(lruNode); // Remove from linked list
                cacheMap.erase(lruNode->key); // Remove from map
                delete lruNode; // And finally, free up that memory!
            }
        }
    }
};
Enter fullscreen mode Exit fullscreen mode

Time & Space Complexity Analysis

"Alright, enough fun, let's talk numbers!"

  • Time Complexity:

    • LRUCache(capacity): O(1). Just initializing a few pointers and our map. No heavy lifting.
    • get(key): O(1) on average.
      • Hash map lookup (cacheMap.find or []) is O(1) on average.
      • Our deleteNode and insertNode helpers are pure pointer manipulation, always O(1).
    • put(key, value): O(1) on average.
      • Hash map operations (lookup, insert, erase) are O(1) on average.
      • deleteNode and insertNode are O(1).
      • Checking capacity and evicting is also constant time.

  • Space Complexity:

    • O(capacity).
      • Our cacheMap stores up to capacity key -> ListNode* pairs.
      • Our doubly linked list stores up to capacity ListNode objects (plus the two dummy nodes).
    • Each ListNode uses constant space for key, value, prev, next.

"So, yes, we achieved that blazing-fast O(1) average time!"

Key Takeaways: The Secrets of the Cache Masters

  • The Power Couple: When you need fast lookups and ordered removals/insertions, a Hash Map combined with a Doubly Linked List is your go-to pattern. It's like the Batman and Robin of data structures!
  • Dummy Nodes are MVPs: Those head and tail sentinels might seem unnecessary, but they elegantly handle edge cases (empty list, single item) by ensuring prev and next pointers are always valid, saving you from null-pointer checks and messy conditional logic.
  • C++ and Memory: Don't forget that if you new something, you eventually need to delete it. Our destructor ~LRUCache() ensures we're not being a memory hoarder. In languages with garbage collection (like Java or Python), this isn't a manual step, but it's crucial for C++.
  • Thinking beyond simple arrays: Many "move to front" or "remove least X" problems often hint at linked lists or other dynamic structures.

I hope this deep dive into the LRU Cache was as enlightening as it was entertaining! May your caches be ever efficient and your evictions swift. Happy coding!

Submission Details:
Author Account: aaradhyanegi009
Time Published: 2026-05-18 00:48:35

Top comments (0)