LeetCode Challenge: 380. Insert Delete GetRandom O(1) - JavaScript Solution 🚀

Top Interview 150

Implementing a data structure that supports insertion, deletion, and random access in O(1) time complexity is a great test of algorithmic design. Let’s break down LeetCode 380: Insert Delete GetRandom O(1) and solve it step by step in JavaScript.

---

🚀 Problem Description

Design a class RandomizedSet that supports the following operations in average O(1) time:

1. insert(val): Inserts an item into the set if it is not already present. Returns true if the item was inserted, and false otherwise.
2. remove(val): Removes an item if it exists in the set. Returns true if the item was removed, and false otherwise.
3. getRandom(): Returns a random element from the current set. Each element must have an equal probability of being returned.

---

💡 Examples

Input:
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]

Output:
[null, true, false, true, 2, true, false, 2]

---

🏆 JavaScript Solution

The challenge is ensuring all three operations work in average O(1) time. To achieve this, we’ll use:

• A hash map for quick lookups and updates.
• An array for constant-time random access.

Implementation

class RandomizedSet {
    constructor() {
        this.map = new Map();
        this.list = [];
    }

    insert(val) {
        if (this.map.has(val)) return false;
        this.map.set(val, this.list.length);
        this.list.push(val);
        return true;
    }

    remove(val) {
        if (!this.map.has(val)) return false;

        let index = this.map.get(val);
        let lastElement = this.list[this.list.length - 1];

        this.list[index] = lastElement;
        this.map.set(lastElement, index);
        this.list.pop();
        this.map.delete(val);

        return true;
    }

    getRandom() {
        let randomIndex = Math.floor(Math.random() * this.list.length);
        return this.list[randomIndex];
    }
}

---

🔍 How It Works

1. Insert:

   • Add the value to the end of the array.
   • Store the value’s index in the map for constant-time lookup.

2. Remove:

   • Replace the element to be removed with the last element in the array.
   • Update the last element’s index in the map.
   • Remove the last element from the array and delete the value from the map.

3. Get Random:

   • Use Math.random() to pick a random index from the array.
   • Return the value at that index.

---

🔑 Complexity Analysis

• Insert: O(1)
  • Add to the array and map.
• Remove: O(1)
  • Swap and pop from the array, update the map.
• Get Random: O(1)
  • Access a random index in the array.

---

📋 Dry Run

Input:

["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]

---

✨ Pro Tips for Interviews

1. Explain the swap logic: Discuss why swapping the element with the last one simplifies removal in O(1).
2. Edge cases: Handle scenarios like:
   • Empty set for getRandom() (guaranteed to have at least one element).
   • Insert duplicate values.
3. Why two structures?: Emphasize the combination of array and map for constant-time operations.

---

📚 Learn More

Check out the detailed explanation and code walkthrough on my Dev.to post:
👉 H-Index - JavaScript Solution

How would you approach designing this data structure? Let’s discuss below! 🚀

JavaScript #LeetCode #CodingInterview #ProblemSolving

Comments

[Nozibul Islam]

great.