How to Deleting Array Element in O(1) Time

labuladongOriginalAbout 4519 words

Note

Now all the plugins has supported English. I'm still improving the website...

This article will resolve

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

Prerequisite Knowledge

Before reading this article, you need to learn:

Array Basics
Array Implementation
Hash Table Basics
Hash Table Implementation
Enhancing Hash Tables with Arrays

This article discusses two data structure design problems that involve some clever techniques, both related to random element retrieval. I have also written about similar issues in the previous article Random Algorithms in Games.

One key point in these problems is how to combine hash tables and arrays so that the time complexity of the delete operation in the array also becomes O(1). Let's go through these problems one by one.

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

Implement Randomized Set

Random Numbers Avoiding a Blacklist