DEV Community

Cover image for LeetCode Challenge: 380. Insert Delete GetRandom O(1) - JavaScript Solution πŸš€
Rahul Kumar Barnwal
Rahul Kumar Barnwal

Posted on

2 2 2 2 2

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]
Enter fullscreen mode Exit fullscreen mode

πŸ† 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];
    }
}
Enter fullscreen mode Exit fullscreen mode

πŸ” 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], []]
Enter fullscreen mode Exit fullscreen mode

Insert Delete GetRandom


✨ 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

Heroku

Build apps, not infrastructure.

Dealing with servers, hardware, and infrastructure can take up your valuable time. Discover the benefits of Heroku, the PaaS of choice for developers since 2007.

Visit Site

Top comments (2)

Collapse
 
rahulgithubweb profile image
Rahul Kumar Barnwal β€’ β€’ Edited

Follow Me on GitHub πŸš€

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!

Collapse
 
nozibul_islam_113b1d5334f profile image
Nozibul Islam β€’

great.

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs

πŸ‘‹ Kindness is contagious

Please leave a ❀️ or a friendly comment on this post if you found it helpful!

Okay