380. Insert Delete GetRandom O(1)

 

Implementing a Randomized Set in JavaScript

Introduction

In the world of data structures, efficiency is key. Today, I’m excited to share a solution for implementing a RandomizedSet in JavaScript. This data structure allows for efficient insertion, deletion, and random retrieval of elements, making it a versatile tool for various applications.

Problem Statement

The goal is to design a data structure that supports the following operations:

  1. insert(val): Inserts a value into the set. Returns true if the set did not already contain the specified element.

  2. remove(val): Removes a value from the set. Returns true if the set contained the specified element.

  3. getRandom(): Returns a random element from the set. Each element must have the same probability of being returned.

Approach

To achieve these functionalities efficiently, we'll utilize JavaScript's Set object, which offers constant time complexity for insertion and deletion. For random retrieval, converting the set to an array and using a random index is a straightforward approach.

1. Initialization:

  • Create an empty Set.

2. Insert:

  • Check if the value already exists in the set. If it does, return false. Otherwise, add the value to the set and return true.

3. Remove:

  • Check if the value exists in the set. If it doesn't, return false. Otherwise, delete the value from the set and return true.

4. Get Random:

  • Convert the set to an array and select a random index to return an element.

Code Implementation

Here's the JavaScript implementation for the RandomizedSet:


var RandomizedSet = function() {
    this.set = new Set();
};

/**
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
    if(this.set.has(val)) {
        return false;
    }
    this.set.add(val);
    return true;
};

/**
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
    if(!this.set.has(val)){
        return false;
    }
    this.set.delete(val);
    return true;
};

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function() {
    let arr = Array.from(this.set);
    const randomIndex = Math.floor(Math.random() * arr.length);
    return arr[randomIndex];
};

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * var obj = new RandomizedSet()
 * var param_1 = obj.insert(val)
 * var param_2 = obj.remove(val)
 * var param_3 = obj.getRandom()
 */

Complexity Analysis

  • Time Complexity:

    • insert: O(1)O(1)

    • remove: O(1)O(1)

    • getRandom: O(1)O(1) on average, although converting the set to an array takes O(n)O(n)

  • Space Complexity: O(n)O(n)

    • The set uses space proportional to the number of elements stored.

Conclusion

The RandomizedSet efficiently supports insertion, deletion, and random retrieval of elements, making it a powerful tool for various applications. By leveraging JavaScript's Set object and array manipulation, we achieve these operations with optimal performance.

For more insights and detailed discussions, you can check out the related LeetCode solution: Insert Delete GetRandom O(1) - LeetCode.

Comments

Post a Comment

Popular posts from this blog

3Sum Closest: O(n²) Two-Pointer Magic 🚀 leetcode: 16

Three Sum Closest - LeetCode Solution In this blog post, we'll dive into the Three Sum Closest problem, a popular coding challenge on LeetCode. We'll explore the intuition behind the solution, discuss the approach, analyze the complexity, and provide a detailed explanation of the code. Additionally, I'll share my LeetCode solution link for further reference. Problem Statement Given an integer array nums of length n and an integer target , find three integers in nums such that the sum is closest to target . Return the sum of the three integers. You may assume that each input would have exactly one solution. Intuition The problem requires finding three numbers in the array whose sum is as close as possible to the target. To efficiently find such a triplet, we can use a combination of sorting and the two-pointer technique . Sorting : First, sort the array. This allows us to use the two-po...
Read more

Kadane's Algorithm: Maximum Subarray Problem - LeetCode(53) Solution

Maximum Subarray Problem - LeetCode Solution Maximum Subarray Problem - LeetCode Solution Problem Statement Given an integer array nums , find the contiguous subarray (containing at least one number) that has the largest sum and return its sum. Intuition The problem requires finding the contiguous subarray with the maximum sum. A brute force approach would involve checking all subarrays, but this would be inefficient. Instead, we use Kadane's Algorithm , which efficiently finds the maximum sum subarray in O(n) time. Approach Initialize two variables: total (running sum) and maxi (maximum sum encountered so far). Iterate through the array: Add the current element to total . Update maxi with the maximum of maxi and total . If total becomes negative, reset it to zero. Return maxi as the maximum sub...
Read more

LeetCode Problem: Implement pow(x, n) leetcode:- 50

Understanding the Fast Exponentiation Algorithm: Exponentiation by Squaring In this blog post, we will explore the implementation of the myPow function, a common problem found on LeetCode. The goal of this problem is to compute \(x^n\) efficiently, even when \(n\) is a very large number. Instead of using a naive approach, we employ a method called Exponentiation by Squaring to significantly reduce the number of multiplications required. Problem Overview Given a floating-point number x and an integer n , our task is to implement a function that computes \(x^n\). A straightforward solution might involve multiplying x by itself n times, but this approach is too slow when n is large. Intuition Behind Exponentiation by Squaring The main idea is to reduce the problem size by halving the exponent at each recursive step. Consider the following: If n is even, then: \(x^n = x^{...
Read more