0380_insert_delete_getrandom_o1.html

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>LC 380: Insert Delete GetRandom O(1) - 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">#380</span> Insert Delete GetRandom O(1)</h1>
            <p>Design a data structure that supports insert, remove, and getRandom in average O(1) time.</p>
            <div class="problem-meta">
                <span class="meta-tag">🔧 Design</span>
                <span class="meta-tag">📊 Hash Map</span>
                <span class="meta-tag">⏱️ O(1) average</span>
                <span class="meta-tag">💾 O(n)</span>
            </div>
            <div class="file-ref">
                📄 Python: <code>python/0380_insert_delete_getrandom_o1/0380_insert_delete_getrandom_o1.py</code>
            </div>
            </div>

        <div class="explanation-panel">
            <h4>🧠 How It Works (Layman's Terms)</h4>
            <p>Combine <strong>Array + HashMap</strong> for O(1) operations:</p>
            <ul>
                <li><strong>Array:</strong> Store values for O(1) random access</li>
                <li><strong>HashMap:</strong> Map value → index for O(1) lookup</li>
                <li><strong>Insert:</strong> Append to array, update map</li>
                <li><strong>Remove:</strong> Swap with last element, pop, update map</li>
                <li><strong>Random:</strong> Pick random index from array</li>
            </ul>
        </div>


        <div class="visualization-section">
            <h3>🎬 Step-by-Step Visualization</h3>
            
            <div class="controls">
                <input type="number" id="valueInput" placeholder="Enter value" style="padding: 8px; width: 120px; border-radius: 5px; border: 2px solid #ddd;">
                <button class="btn btn-primary" onclick="insertValue()">Insert</button>
                <button class="btn btn-warning" onclick="removeValue()">Remove</button>
                <button class="btn" style="background: #9c27b0; color: white;" onclick="getRandom()">🎲 GetRandom</button>
                <button class="btn" onclick="reset()">Reset</button>
            </div>

            <div class="status-message" id="statusMessage">
                Enter a value and click Insert, Remove, or GetRandom
            </div>

            <div style="display: flex; gap: 30px; flex-wrap: wrap; margin-top: 20px;">
                <div style="flex: 1; min-width: 300px;">
                    <h4>📊 Array (for O(1) random)</h4>
                    <div id="arrayDisplay" style="display: flex; flex-wrap: wrap; gap: 10px; padding: 20px; background: #e3f2fd; border-radius: 12px; min-height: 80px;"></div>
                    <div style="margin-top: 10px; font-size: 0.9em; color: #666;">
                        Indices: <span id="indexDisplay"></span>
                    </div>
                </div>
                <div style="flex: 1; min-width: 250px;">
                    <h4>🗺️ HashMap (value → index)</h4>
                    <div id="mapDisplay" style="padding: 15px; background: #fff3e0; border-radius: 12px; min-height: 80px;"></div>
                </div>
            </div>

            <div id="animationBox" style="margin-top: 20px; padding: 20px; background: #f5f5f5; border-radius: 12px; display: none;">
                <h4 style="margin-bottom: 10px;">🔄 Operation Details</h4>
                <div id="animationSteps" style="font-family: monospace;"></div>
            </div>
        </div>

        <div class="code-section">
            <h3>💻 Python Solution</h3>
            <div class="code-block">
                <pre>from typing import List
import random


"""
LeetCode Insert Delete GetRandom O(1)

Problem from LeetCode: https://leetcode.com/problems/insert-delete-getrandom-o1/

Description:
Implement the RandomizedSet class:
- RandomizedSet() Initializes the RandomizedSet object.
- bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
- bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
- int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

Example 1:
Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Constraints:
-2^31 &lt;= val &lt;= 2^31 - 1
At most 2 * 10^5 calls will be made to insert, remove, and getRandom.
There will be at least one element in the data structure when getRandom is called.
"""

class RandomizedSet:
    """
    A data structure that supports insert, remove, and getRandom operations in O(1) time.
    """

    def __init__(self):
        """
        Initialize your data structure here.
        """
        # Dictionary to store val -&gt; index mapping for O(1) lookup
        self.val_to_idx = {}
        # List to store values for O(1) random access
        self.values = []

    def insert(self, val: int) -&gt; bool:
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        
        Args:
            val: Value to insert
            
        Returns:
            bool: True if the value was not present, False otherwise
        """
        if val in self.val_to_idx:
            return False
        
        # Add value to the end of the list
        self.values.append(val)
        # Store the index in the dictionary
        self.val_to_idx[val] = len(self.values) - 1
        return True

    def remove(self, val: int) -&gt; bool:
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        
        Args:
            val: Value to remove
            
        Returns:
            bool: True if the value was present, False otherwise
        """
        if val not in self.val_to_idx:
            return False
        
        # Get the index of the value to remove
        idx = self.val_to_idx[val]
        last_val = self.values[-1]
        
        # Move the last element to the position of the element to remove
        self.values[idx] = last_val
        self.val_to_idx[last_val] = idx
        
        # Remove the last element and the value from the dictionary
        self.values.pop()
        del self.val_to_idx[val]
        
        return True

    def get_random(self) -&gt; int:
        """
        Get a random element from the set.
        
        Returns:
            int: A random element from the set
        """
        return random.choice(self.values)


if __name__ == '__main__':
    # Example usage based on LeetCode sample
    randomizedSet = RandomizedSet()
    
    # Test the operations
    print(randomizedSet.insert(1))   # Returns true as 1 was inserted successfully
    print(randomizedSet.remove(2))   # Returns false as 2 does not exist in the set
    print(randomizedSet.insert(2))   # Inserts 2 to the set, returns true
    
    # getRandom should return either 1 or 2 randomly
    random_val = randomizedSet.get_random()
    print(f"Random value: {random_val}")  # Will be either 1 or 2
    
    print(randomizedSet.remove(1))   # Removes 1 from the set, returns true
    print(randomizedSet.insert(2))   # 2 was already in the set, so return false
    
    # Since 2 is the only number in the set, getRandom will always return 2
    print(f"Random value: {randomizedSet.get_random()}")  # Will always be 2
    
    # Additional tests
    print("\nAdditional tests:")
    randomizedSet.insert(3)
    randomizedSet.insert(4)
    randomizedSet.insert(5)
    
    print("Current set:", randomizedSet.values)
    print("Random value:", randomizedSet.get_random())  # Will be one of 2, 3, 4, or 5
    
    print("Remove 3:", randomizedSet.remove(3))
    print("Current set after removing 3:", randomizedSet.values)
</pre>
            </div>
        </div>
    </div>

    <script>
        let arr = [];
        let valToIdx = {};
        let highlightedIdx = -1;
        let highlightedVal = null;

        function render() {
            // Render array
            const arrayContainer = document.getElementById('arrayDisplay');
            if (arr.length === 0) {
                arrayContainer.innerHTML = '<span style="color: #999;">(empty)</span>';
                document.getElementById('indexDisplay').textContent = '';
            } else {
                arrayContainer.innerHTML = arr.map((val, i) => {
                    let bg = '#667eea';
                    if (i === highlightedIdx) bg = '#4caf50';
                    if (val === highlightedVal) bg = '#ff9800';
                    return `<div style="padding: 15px 20px; background: ${bg}; color: white; border-radius: 10px; font-weight: bold; font-size: 1.2em; transition: all 0.3s; text-align: center; min-width: 40px;">${val}</div>`;
                }).join('');
                document.getElementById('indexDisplay').textContent = arr.map((_, i) => i).join('  |  ');
            }

            // Render hashmap
            const mapContainer = document.getElementById('mapDisplay');
            const entries = Object.entries(valToIdx);
            if (entries.length === 0) {
                mapContainer.innerHTML = '<span style="color: #999;">(empty)</span>';
            } else {
                mapContainer.innerHTML = entries.map(([val, idx]) => {
                    let bg = '#ffcc80';
                    if (parseInt(val) === highlightedVal) bg = '#ff9800';
                    return `<div style="display: inline-block; padding: 8px 15px; margin: 4px; background: ${bg}; border-radius: 8px; font-family: monospace;">
                        ${val} → ${idx}
                    </div>`;
                }).join('');
            }
        }

        function showAnimation(steps) {
            const box = document.getElementById('animationBox');
            box.style.display = 'block';
            document.getElementById('animationSteps').innerHTML = steps.map((s, i) => 
                `<div style="padding: 5px 0; ${i === steps.length - 1 ? 'color: #4caf50; font-weight: bold;' : ''}">${i + 1}. ${s}</div>`
            ).join('');
        }

        function hideAnimation() {
            document.getElementById('animationBox').style.display = 'none';
        }

        function insertValue() {
            const input = document.getElementById('valueInput');
            const val = parseInt(input.value);
            if (isNaN(val)) {
                document.getElementById('statusMessage').textContent = 'Please enter a valid number';
                return;
            }

            highlightedIdx = -1;
            highlightedVal = val;

            if (val in valToIdx) {
                document.getElementById('statusMessage').textContent = `❌ Insert(${val}): Already exists, return False`;
                showAnimation([
                    `Check if ${val} in HashMap: YES`,
                    `Return False (duplicate)`
                ]);
            } else {
                arr.push(val);
                valToIdx[val] = arr.length - 1;
                highlightedIdx = arr.length - 1;
                document.getElementById('statusMessage').textContent = `✅ Insert(${val}): Added at index ${arr.length - 1}, return True`;
                showAnimation([
                    `Check if ${val} in HashMap: NO`,
                    `Append ${val} to array`,
                    `Add to HashMap: ${val} → ${arr.length - 1}`,
                    `Return True`
                ]);
            }

            input.value = '';
            render();
            setTimeout(() => { highlightedIdx = -1; highlightedVal = null; render(); }, 1500);
        }

        function removeValue() {
            const input = document.getElementById('valueInput');
            const val = parseInt(input.value);
            if (isNaN(val)) {
                document.getElementById('statusMessage').textContent = 'Please enter a valid number';
                return;
            }

            highlightedIdx = -1;
            highlightedVal = val;

            if (!(val in valToIdx)) {
                document.getElementById('statusMessage').textContent = `❌ Remove(${val}): Not found, return False`;
                showAnimation([
                    `Check if ${val} in HashMap: NO`,
                    `Return False (not found)`
                ]);
            } else {
                const idx = valToIdx[val];
                const last = arr[arr.length - 1];
                const steps = [
                    `Find index of ${val}: ${idx}`,
                    `Last element: ${last}`
                ];

                if (idx !== arr.length - 1) {
                    arr[idx] = last;
                    valToIdx[last] = idx;
                    steps.push(`Swap: arr[${idx}] = ${last}`);
                    steps.push(`Update HashMap: ${last} → ${idx}`);
                }

                arr.pop();
                delete valToIdx[val];
                steps.push(`Pop last element from array`);
                steps.push(`Delete ${val} from HashMap`);
                steps.push(`Return True`);

                document.getElementById('statusMessage').textContent = `✅ Remove(${val}): Removed successfully, return True`;
                showAnimation(steps);
            }

            input.value = '';
            render();
            setTimeout(() => { highlightedIdx = -1; highlightedVal = null; render(); }, 1500);
        }

        function getRandom() {
            if (arr.length === 0) {
                document.getElementById('statusMessage').textContent = '❌ GetRandom: Set is empty!';
                hideAnimation();
                return;
            }

            const randomIdx = Math.floor(Math.random() * arr.length);
            const randomVal = arr[randomIdx];
            highlightedIdx = randomIdx;
            highlightedVal = randomVal;

            document.getElementById('statusMessage').textContent = `🎲 GetRandom(): Picked index ${randomIdx}, value = ${randomVal}`;
            showAnimation([
                `Array length: ${arr.length}`,
                `Random index: ${randomIdx}`,
                `arr[${randomIdx}] = ${randomVal}`,
                `Return ${randomVal}`
            ]);

            render();
            setTimeout(() => { highlightedIdx = -1; highlightedVal = null; render(); }, 1500);
        }

        function reset() {
            arr = [];
            valToIdx = {};
            highlightedIdx = -1;
            highlightedVal = null;
            document.getElementById('statusMessage').textContent = 'Enter a value and click Insert, Remove, or GetRandom';
            document.getElementById('valueInput').value = '';
            hideAnimation();
            render();
        }

        document.getElementById('valueInput').addEventListener('keypress', (e) => {
            if (e.key === 'Enter') insertValue();
        });

        reset();
    </script>
</body>
</html>