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