[LeetCode][380. Insert Delete GetRandom O(1)] Data Structures: Thought Process from HashMap to HashMap + Array

By Long Luo

This article is the solution Data Structures: Thought Process from HashMap to HashMap + Array of Problem 380. Insert Delete GetRandom O(1) .

Intuition

It’s easy to think of using a Hash Table to achieve $O(1)$ time complexity for $\mathtt{\text{insert}}$ and $\mathtt{\text{remove}}$ operations. However, we need $O(1)$ time complexity to complete the $\mathtt{\text{getRandom}}$ operation.

The Array structure can complete the operation of obtaining random elements in $O(1)$ time complexity, but it can’t completed the $\mathtt{\text{insert}}$ and $\mathtt{\text{remove}}$ operations in $O(1)$ time complexity.

So How?

Aha!!!

We can combining the $\mathtt{\text{HashMap}}$ and Array. The Array stores the elements, and the $\mathtt{\text{HashMap}}$ stores the input value as the $\mathtt{\text{key}}$ and the array subscript $\mathtt{\text{loc}}$ as the value.

We need to apply for an array nums of sufficient size (the data range is $2\times {10}^5$ ), and a variable $\mathtt{\text{idx}}$ to record how many space is currently used.

• $\mathtt{\text{insert}}$: Judge whether the $\mathtt{\text{HashMap}}$ contains the $\mathtt{\text{val}}$, if not, insert the $\mathtt{\text{val}}$ to the $\mathtt{\text{HashMap}}$ and update the Array nums.

• $\mathtt{\text{remove}}$: Judge whether the $\mathtt{\text{HashMap}}$ contains the $\mathtt{\text{val}}$, if not, get the location loc of the input val, replace the loc with the last value of the array, remove the $\mathtt{\text{val}}$ from $\mathtt{\text{HashMap}}$ and update the $\mathtt{\text{idx}}$.

• $\mathtt{\text{getRandom}}$: Just select a subscript at random and return the element of the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

class RandomizedSet {
    Map<Integer, Integer> map;
    int[] nums;
    int idx;
    Random random;

    public RandomizedSet() {
        map = new HashMap<>();
        nums = new int[2_00_002];
        idx = 0;
        random = new Random();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }

        nums[idx] = val;
        map.put(val, idx);
        idx++;
        return true;
    }

    public boolean remove(int val) {
        if (map.containsKey(val)) {
            int loc = map.get(val);
            map.remove(val);

            if (loc != idx - 1) {
                nums[loc] = nums[idx - 1];
                map.put(nums[idx - 1], loc);
            }

            idx--;
            return true;
        }

        return false;
    }

    public int getRandom() {
        int loc = random.nextInt(idx);
        return nums[loc];
    }
}

Analysis

• Time Complexity: $O(1)$.
• Space Complexity: $O(n)$.

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗