Practice/Udemy/Leetcode 380. Insert Delete GetRandom O(1)

Leetcode 380. Insert Delete GetRandom O(1)

CodingMust

Problem

Build a data structure that maintains a collection of unique integers and supports three operations, each completing in average O(1) time complexity:

1. insert(val): Add an integer to the collection. Return true if the value was not already present (insertion succeeded), false if it already exists (insertion failed).
2. remove(val): Delete an integer from the collection. Return true if the value was present (removal succeeded), false if it wasn't found (removal failed).
3. getRandom(): Return a random element from the current collection where each element has equal probability of being selected.

The challenging aspect is achieving constant time for all operations while maintaining uniform random selection. Traditional data structures excel at some operations but not all three simultaneously.

Requirements

1. Each operation must run in average O(1) time complexity
2. The insert operation should prevent duplicates
3. The remove operation should only succeed if the element exists
4. The getRandom operation must give each current element equal probability
5. Handle any valid integer values within the language's integer range

Constraints

• Number of operations: 1 ≤ ops ≤ 2 × 10^5
• Value range: -2^31 ≤ val ≤ 2^31 - 1
• getRandom will only be called when at least one element exists in the collection
• All three operations must average O(1) time complexity

Examples

Example 1: Basic functionality

` Operations: ["RandomSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] Parameters: [[], [1], [2], [2], [], [1], [2], []]

Output: [null, true, false, true, 2, true, true, 2]

Explanation:

• RandomSet() initializes empty collection
• insert(1) adds 1, returns true (success)
• remove(2) tries to remove non-existent element, returns false
• insert(2) adds 2, returns true (success) — collection now {1, 2}
• getRandom() returns either 1 or 2 randomly
• remove(1) removes 1, returns true (success) — collection now {2}
• insert(2) tries to add duplicate, returns false
• getRandom() returns 2 (only element) `

Example 2: Duplicate handling

` Operations: ["RandomSet", "insert", "insert", "insert", "getRandom"] Parameters: [[], [5], [5], [10], []]

Output: [null, true, false, true, 5 or 10]

Explanation:

• insert(5) succeeds, returns true
• insert(5) fails (duplicate), returns false
• insert(10) succeeds, returns true
• getRandom() returns 5 or 10 with equal probability `

Example 3: Removal from empty collection

` Operations: ["RandomSet", "remove", "insert", "getRandom", "remove"] Parameters: [[], [100], [100], [], [100]]

Output: [null, false, true, 100, true]

Explanation:

• remove(100) from empty collection fails, returns false
• insert(100) succeeds, returns true
• getRandom() returns 100 (only element)
• remove(100) succeeds, returns true `