How to Deleting Array Element in O(1) Time

This article will resolve

LeetCode	Difficulty
380. Insert Delete GetRandom O(1)	🟠
710. Random Pick with Blacklist	🔴

Prerequisites

Before reading this article, you should first study:

Enhancing Hash Tables with Arrays

This article discusses two data structure design problems that require some skillful techniques, both related to random element access. I have also covered similar issues in a previous article on Random Algorithms in Games.

A key challenge in these problems is how to combine hash tables and arrays to make the deletion operation in an array also O(1)? Let's examine each problem in turn.

How to Deleting Array Element in O(1) Time

380. Insert Delete GetRandom O(1) https://leetcode.com/problems/insert-delete-getrandom-o1

710. Random Pick with Blacklist https://leetcode.com/problems/random-pick-with-blacklist

Implementing a Randomized Set

Random Number Without Blacklist