0146_lru_cache.html

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>LC 146: LRU Cache - Algorithm Visualization</title>
    <link rel="stylesheet" href="styles.css">
    <script src="https://d3js.org/d3.v7.min.js"></script>
</head>
<body>
    <div class="container">
        <div class="problem-info">
            <h1><span class="problem-number">#146</span> LRU Cache</h1>
            <p>Design a data structure that follows Least Recently Used (LRU) cache constraints. Implement get and put operations in O(1) time.</p>
            <div class="problem-meta">
                <span class="meta-tag">🎨 Design</span>
                <span class="meta-tag">🔗 Linked List</span>
                <span class="meta-tag">📚 HashMap</span>
                <span class="meta-tag">⏱️ O(1)</span>
            </div>
            <div class="file-ref">
                📄 Python: <code>python/0146_lru_cache/0146_lru_cache.py</code>
            </div>
            </div>

        <div class="explanation-panel">
            <h4>🧠 How It Works (Layman's Terms)</h4>
            <p>LRU Cache combines a <strong>HashMap + Doubly Linked List</strong>:</p>
            <ul>
                <li><strong>HashMap:</strong> O(1) lookup by key → node</li>
                <li><strong>Doubly Linked List:</strong> O(1) remove/insert for ordering</li>
                <li><strong>Head = Most Recent:</strong> Recently accessed items go to the front</li>
                <li><strong>Tail = Least Recent:</strong> When cache is full, evict from the back</li>
            </ul>
        </div>


        <div class="visualization-section">
            <h3>🎬 Step-by-Step Visualization</h3>
            
            <div class="controls">
                <input type="number" id="keyInput" placeholder="Key" style="width: 60px; padding: 8px; border-radius: 5px; border: 2px solid #ddd;">
                <input type="number" id="valueInput" placeholder="Val" style="width: 60px; padding: 8px; border-radius: 5px; border: 2px solid #ddd;">
                <button class="btn btn-primary" onclick="putOp()">Put</button>
                <button class="btn btn-success" onclick="getOp()">Get</button>
                <button class="btn" style="background: #607d8b; color: white;" onclick="reset()">Reset</button>
            </div>

            <div class="status-message" id="statusMessage">
                Enter a key-value pair and click Put, or enter a key and click Get
            </div>

            <div style="display: flex; gap: 30px; flex-wrap: wrap; margin-top: 20px;">
                <div style="flex: 1; min-width: 300px;">
                    <h4 style="margin-bottom: 10px;">🔗 Doubly Linked List (Most Recent → Least Recent)</h4>
                    <svg id="listViz" width="100%" height="120"></svg>
                </div>
                <div style="flex: 1; min-width: 200px;">
                    <h4 style="margin-bottom: 10px;">📚 HashMap</h4>
                    <div id="hashContainer" style="padding: 15px; background: #f5f5f5; border-radius: 12px; min-height: 100px;">
                        <span style="color: #999;">Empty</span>
                    </div>
                </div>
            </div>

            <div style="margin-top: 20px;">
                <h4 style="margin-bottom: 10px;">📝 Operations Log</h4>
                <div id="logContainer" style="padding: 15px; background: #f5f5f5; border-radius: 12px; max-height: 200px; overflow-y: auto;">
                    <div style="color: #999;">Operations will appear here...</div>
                </div>
            </div>

            <div class="info-box" style="margin-top: 20px;">
                <h4>🔑 Try This Sequence</h4>
                <p>Put(1,1) → Put(2,2) → Get(1) → Put(3,3) → Get(2) → Put(4,4)</p>
                <p>Watch how items move to front on access, and how LRU items get evicted!</p>
            </div>
        </div>
        <div class="code-section">
            <h3>💻 Python Solution</h3>
            <div class="code-block">
                <pre>from typing import List, Optional

"""
LeetCode LRU Cache

Problem from LeetCode: https://leetcode.com/problems/lru-cache/

Description:
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:
- LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
- int get(int key) Return the value of the key if the key exists, otherwise return -1.
- void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example:
Input:
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output:
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation:
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4
"""

class Node:
    """
    Doubly linked list node to store key-value pairs and maintain order.
    """

    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class LRUCache:
    """
    LRU Cache implementation using a hash map and a doubly linked list.
    The hash map provides O(1) access to cache items, while the doubly linked list
    maintains the order of items for efficient LRU eviction.
    """
    def __init__(self, capacity: int):
        """
        Initialize the LRU cache with the given capacity.
        
        Args:
            capacity: Maximum number of key-value pairs the cache can hold
        """
        self.capacity = capacity
        self.cache = {}
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key: int) -&gt; int:
        """
        Retrieve the value of the key if it exists in the cache.
        This operation also makes the key the most recently used.
        
        Args:
            key: Key to look up in the cache
            
        Returns:
            int: Value associated with the key, or -1 if the key doesn't exist
        """
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._insert_at_head(node)
        return node.value

    def put(self, key: int, value: int) -&gt; None:
        """
        Insert or update the value of a key in the cache.
        If the key already exists, update its value and make it the most recently used.
        If the key doesn't exist, add it to the cache. If this causes the cache to
        exceed its capacity, remove the least recently used item.
        
        Args:
            key: Key to insert or update
            value: Value to associate with the key
        """
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._remove(node)
            self._insert_at_head(node)
        else:
            if len(self.cache) == self.capacity:
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]
            new_node = Node(key, value)
            self.cache[key] = new_node
            self._insert_at_head(new_node)

    def _remove(self, node: Node) -&gt; None:
        """
        Remove a node from the doubly linked list.
        
        Args:
            node: Node to remove
        """
        node.prev.next = node.next
        node.next.prev = node.prev

    def _insert_at_head(self, node: Node) -&gt; None:
        """
        Insert a node at the head of the doubly linked list (most recently used).
        
        Args:
            node: Node to insert
        """
        node.next = self.head.next
        node.next.prev = node
        self.head.next = node
        node.prev = self.head


if __name__ == '__main__':
    # Example usage based on LeetCode sample
    lru_cache = LRUCache(2)
    
    operations = [
        "put", "put", "get", "put", "get", "put", "get", "get", "get"
    ]
    params = [
        [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]
    ]
    
    results = []
    for i, op in enumerate(operations):
        if op == "put":
            lru_cache.put(params[i][0], params[i][1])
            results.append(None)
        elif op == "get":
            result = lru_cache.get(params[i][0])
            results.append(result)
    
    print("Operations:", operations)
    print("Parameters:", params)
    print("Results:", results)
    # Expected output: [None, None, 1, None, -1, None, -1, 3, 4]
</pre>
            </div>
        </div>
    </div>

    <script>
        const capacity = 2;
        let cache = new Map(); // key → {key, value}
        let order = []; // Array representing the list order (head to tail)
        let logs = [];

        function drawList() {
            const svg = d3.select("#listViz");
            svg.selectAll("*").remove();

            const container = svg.node().parentElement;
            const width = container.clientWidth;
            const height = 120;
            svg.attr("viewBox", `0 0 ${width} ${height}`);

            const g = svg.append("g");
            const nodeWidth = 80;
            const nodeHeight = 50;
            const gap = 60;

            // Draw dummy head
            const headX = 30;
            g.append("rect")
                .attr("x", headX)
                .attr("y", 35)
                .attr("width", 40)
                .attr("height", 40)
                .attr("fill", "#e0e0e0")
                .attr("stroke", "#bdbdbd")
                .attr("stroke-width", 2)
                .attr("rx", 5);
            g.append("text")
                .attr("x", headX + 20)
                .attr("y", 60)
                .attr("text-anchor", "middle")
                .attr("font-size", "12px")
                .attr("fill", "#666")
                .text("HEAD");

            let x = headX + 40 + gap;

            // Draw nodes
            order.forEach((item, i) => {
                // Arrow from previous
                g.append("line")
                    .attr("x1", x - gap + 10)
                    .attr("y1", 55)
                    .attr("x2", x - 10)
                    .attr("y2", 55)
                    .attr("stroke", "#667eea")
                    .attr("stroke-width", 2)
                    .attr("marker-end", "url(#arrowhead)");

                // Node
                const isFirst = i === 0;
                const isLast = i === order.length - 1;

                g.append("rect")
                    .attr("x", x)
                    .attr("y", 30)
                    .attr("width", nodeWidth)
                    .attr("height", nodeHeight)
                    .attr("fill", isFirst ? "#4caf50" : (isLast ? "#ffcdd2" : "#667eea"))
                    .attr("stroke", isFirst ? "#388e3c" : (isLast ? "#ef9a9a" : "#5a6fd6"))
                    .attr("stroke-width", 2)
                    .attr("rx", 8);

                g.append("text")
                    .attr("x", x + nodeWidth / 2)
                    .attr("y", 50)
                    .attr("text-anchor", "middle")
                    .attr("font-size", "14px")
                    .attr("font-weight", "bold")
                    .attr("fill", "white")
                    .text(`K:${item.key}`);

                g.append("text")
                    .attr("x", x + nodeWidth / 2)
                    .attr("y", 68)
                    .attr("text-anchor", "middle")
                    .attr("font-size", "12px")
                    .attr("fill", "white")
                    .text(`V:${item.value}`);

                // Label
                if (isFirst) {
                    g.append("text")
                        .attr("x", x + nodeWidth / 2)
                        .attr("y", 20)
                        .attr("text-anchor", "middle")
                        .attr("font-size", "10px")
                        .attr("fill", "#4caf50")
                        .text("Most Recent");
                }
                if (isLast) {
                    g.append("text")
                        .attr("x", x + nodeWidth / 2)
                        .attr("y", 100)
                        .attr("text-anchor", "middle")
                        .attr("font-size", "10px")
                        .attr("fill", "#f44336")
                        .text("LRU (evict next)");
                }

                x += nodeWidth + gap;
            });

            // Arrow to tail
            if (order.length > 0) {
                g.append("line")
                    .attr("x1", x - gap + 10)
                    .attr("y1", 55)
                    .attr("x2", x - 10)
                    .attr("y2", 55)
                    .attr("stroke", "#667eea")
                    .attr("stroke-width", 2)
                    .attr("marker-end", "url(#arrowhead)");
            } else {
                g.append("line")
                    .attr("x1", headX + 50)
                    .attr("y1", 55)
                    .attr("x2", x - 10)
                    .attr("y2", 55)
                    .attr("stroke", "#667eea")
                    .attr("stroke-width", 2)
                    .attr("marker-end", "url(#arrowhead)");
            }

            // Draw dummy tail
            g.append("rect")
                .attr("x", x)
                .attr("y", 35)
                .attr("width", 40)
                .attr("height", 40)
                .attr("fill", "#e0e0e0")
                .attr("stroke", "#bdbdbd")
                .attr("stroke-width", 2)
                .attr("rx", 5);
            g.append("text")
                .attr("x", x + 20)
                .attr("y", 60)
                .attr("text-anchor", "middle")
                .attr("font-size", "12px")
                .attr("fill", "#666")
                .text("TAIL");

            // Arrow marker
            svg.append("defs").append("marker")
                .attr("id", "arrowhead")
                .attr("viewBox", "0 -5 10 10")
                .attr("refX", 5)
                .attr("refY", 0)
                .attr("markerWidth", 6)
                .attr("markerHeight", 6)
                .attr("orient", "auto")
                .append("path")
                .attr("d", "M0,-5L10,0L0,5")
                .attr("fill", "#667eea");
        }

        function renderHash() {
            const container = document.getElementById('hashContainer');
            if (cache.size === 0) {
                container.innerHTML = '<span style="color: #999;">Empty</span>';
                return;
            }
            container.innerHTML = Array.from(cache.entries()).map(([key, item]) => `
                <div style="padding: 8px 12px; margin: 5px 0; background: #e3f2fd; 
                            border-radius: 6px; display: flex; justify-content: space-between;">
                    <span>Key: <strong>${key}</strong></span>
                    <span>→ Node(${key}, ${item.value})</span>
                </div>
            `).join('');
        }

        function addLog(op, msg, color = '#e3f2fd') {
            logs.push({ op, msg, color });
            if (logs.length > 15) logs.shift();
            renderLogs();
        }

        function renderLogs() {
            const container = document.getElementById('logContainer');
            if (logs.length === 0) {
                container.innerHTML = '<div style="color: #999;">Operations will appear here...</div>';
                return;
            }
            container.innerHTML = logs.map(log => `
                <div style="padding: 8px; margin: 3px 0; background: ${log.color}; 
                            border-radius: 5px; font-size: 0.9em;">
                    <strong>${log.op}:</strong> ${log.msg}

        </div>
            `).join('');
            container.scrollTop = container.scrollHeight;
        }

        function putOp() {
            const key = parseInt(document.getElementById('keyInput').value);
            const value = parseInt(document.getElementById('valueInput').value);
            
            if (isNaN(key) || isNaN(value)) {
                document.getElementById('statusMessage').textContent = '⚠️ Please enter valid key and value';
                return;
            }

            let msg = '';

            if (cache.has(key)) {
                // Update existing
                const idx = order.findIndex(item => item.key === key);
                order.splice(idx, 1);
                msg = `Updated key ${key} to value ${value}. Moved to front.`;
            } else if (cache.size >= capacity) {
                // Evict LRU
                const lru = order.pop();
                cache.delete(lru.key);
                msg = `Cache full! Evicted LRU (key ${lru.key}). Added key ${key}.`;
                addLog('EVICT', `Removed key ${lru.key}`, '#ffebee');
            } else {
                msg = `Added key ${key} with value ${value}`;
            }

            const newItem = { key, value };
            cache.set(key, newItem);
            order.unshift(newItem);

            document.getElementById('statusMessage').textContent = msg;
            addLog('PUT', `put(${key}, ${value})`, '#e8f5e9');

            drawList();
            renderHash();
        }

        function getOp() {
            const key = parseInt(document.getElementById('keyInput').value);
            
            if (isNaN(key)) {
                document.getElementById('statusMessage').textContent = '⚠️ Please enter a valid key';
                return;
            }

            if (!cache.has(key)) {
                document.getElementById('statusMessage').textContent = `Get(${key}): -1 (not found)`;
                addLog('GET', `get(${key}) → -1 (not found)`, '#fff3e0');
                return;
            }

            const item = cache.get(key);
            const idx = order.findIndex(i => i.key === key);
            order.splice(idx, 1);
            order.unshift(item);

            document.getElementById('statusMessage').textContent = 
                `Get(${key}): ${item.value}. Moved to front (most recent).`;
            addLog('GET', `get(${key}) → ${item.value}`, '#e3f2fd');

            drawList();
            renderHash();
        }

        function reset() {
            cache = new Map();
            order = [];
            logs = [];

            document.getElementById('keyInput').value = '';
            document.getElementById('valueInput').value = '';
            document.getElementById('statusMessage').textContent = 
                'Enter a key-value pair and click Put, or enter a key and click Get';
            
            drawList();
            renderHash();
            renderLogs();
        }

        reset();
        window.addEventListener('resize', drawList);
    </script>
</body>
</html>