[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)O(1) time complexity for insert\texttt{insert} and remove\texttt{remove} operations. However, we need O(1)O(1) time complexity to complete the getRandom\texttt{getRandom} operation.

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

So How?

Aha!!!

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

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

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

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

  • getRandom\texttt{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)O(1).
  • Space Complexity: O(n)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. 😉😃💗