How to Deleting Array Element in O(1) Time

labuladongOriginalAbout 4500 words

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. O(1) 时间插入、删除和获取随机元素 https://leetcode.cn/problems/insert-delete-getrandom-o1

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

710. 黑名单中的随机数 https://leetcode.cn/problems/random-pick-with-blacklist

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

Implementing a Randomized Set

Random Number Without Blacklist