By Long Luo

Intuition

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

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

So How?

Aha!!!

We can combining the $\texttt{HashMap}$ and Array. The Array stores the elements, and the $\texttt{HashMap}$ stores the input value as the $\texttt{key}$ and the array subscript $\texttt{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 $\texttt{idx}$ to record how many space is currently used.

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

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

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

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. 😉😃💗