Insert Delete GetRandom O(1)

▶

Steps

setup

Initialize / Setup

Create an empty array to hold elements and an empty hash map to track element indices.

💡 Starting with empty data structures is essential to build the set incrementally and maintain O(1) operations.

Line:

self.nums = []
self.pos = {}

💡 The algorithm uses two data structures working together: an array for random access and a hash map for index lookup.

insert

Insert 1 - Check if 1 exists

Check if the value 1 is already in the hash map to avoid duplicates.

💡 This check prevents inserting duplicates, preserving set semantics.

Line:

if val in self.pos:
    return False

💡 Since 1 is not present, insertion can proceed.

insert

Insert 1 - Append to array and update map

Append 1 to the array and record its index (0) in the hash map.

💡 Appending to the array keeps elements contiguous for random access; updating the map tracks the element's position.

Line:

self.pos[val] = len(self.nums)
self.nums.append(val)

💡 The element 1 is now stored at index 0, enabling O(1) access and removal.

insert

Insert 2 - Check if 2 exists

Check if the value 2 is already in the hash map to avoid duplicates.

💡 Again, this check ensures no duplicates are inserted.

Line:

if val in self.pos:
    return False

💡 Since 2 is not present, insertion can proceed.

insert

Insert 2 - Append to array and update map

Append 2 to the array and record its index (1) in the hash map.

💡 This keeps the array and map consistent for quick access.

Line:

self.pos[val] = len(self.nums)
self.nums.append(val)

💡 The element 2 is now stored at index 1.

getRandom

getRandom - Pick random index

Randomly select an index from the array to return an element.

💡 Random selection from the array ensures uniform probability for each element.

Line:

return random.choice(self.nums)

💡 The random element returned is either 1 or 2, as both are present.

remove

Remove 1 - Check if 1 exists

Check if the value 1 is in the hash map to confirm it can be removed.

💡 Removal only proceeds if the element exists.

Line:

if val not in self.pos:
    return False

💡 Element 1 is present and can be removed.

remove

Remove 1 - Swap with last element and update map

Swap element 1 at index 0 with last element 2 at index 1, update map for 2.

💡 Swapping avoids costly shifts in the array, maintaining O(1) removal.

Line:

idx = self.pos[val]
last_element = self.nums[-1]
self.nums[idx] = last_element
self.pos[last_element] = idx

💡 Element 2 moves to index 0, replacing 1's position.

remove

Remove 1 - Pop last element and delete from map

Remove last element from array and delete 1 from the hash map.

💡 Popping last element finalizes removal without shifting elements.

Line:

self.nums.pop()
del self.pos[val]

💡 Element 1 is fully removed; array and map reflect current state.

getRandom

getRandom - Return remaining element

Randomly select an index from the array, which now contains only element 2.

💡 With one element left, getRandom always returns 2.

Line:

return random.choice(self.nums)

💡 The only element 2 is returned, confirming correct removal of 1.

import random

class RandomizedSet:
    def __init__(self):
        self.nums = []  # STEP 1
        self.pos = {}   # STEP 1

    def insert(self, val: int) -> bool:
        if val in self.pos:  # STEP 2,4
            return False
        self.pos[val] = len(self.nums)  # STEP 3,5
        self.nums.append(val)            # STEP 3,5
        return True

    def remove(self, val: int) -> bool:
        if val not in self.pos:  # STEP 7
            return False
        idx = self.pos[val]      # STEP 8
        last_element = self.nums[-1]  # STEP 8
        self.nums[idx] = last_element  # STEP 8
        self.pos[last_element] = idx   # STEP 8
        self.nums.pop()                # STEP 9
        del self.pos[val]             # STEP 9
        return True

    def getRandom(self) -> int:
        return random.choice(self.nums)  # STEP 6,10

if __name__ == '__main__':
    rs = RandomizedSet()
    print(rs.insert(1))  # STEP 2-3
    print(rs.insert(2))  # STEP 4-5
    print(rs.getRandom())  # STEP 6
    print(rs.remove(1))  # STEP 7-9
    print(rs.getRandom())  # STEP 10

📊

Insert Delete GetRandom O(1) - Watch the Algorithm Execute, Step by Step

Watching each operation unfold visually reveals how the data structures work together to achieve O(1) complexity, which is difficult to grasp from code alone.

setup

empty map

lookup

Lookup: 1

empty map

insert

1→0

Result: true

lookup

Lookup: 2

1→0

insert

1→0

2→1

Result: true

check

1→0

2→1

Result: 1

lookup

Lookup: 1→ 0

1→0lookup

2→1

update

Lookup: 1→ 0

1→0lookup

2→0

delete

Lookup: 1→ 0

2→0

Result: true

check

2→0

Result: 2

Key Takeaways

✓ Combining a hash map and array enables O(1) insert, delete, and random access.

This synergy is hard to see from code alone because it requires understanding how two data structures coordinate.

✓ The swap-delete trick avoids costly array shifts during removals.

Visualizing the swap clarifies why removal remains O(1) despite using an array.

✓ getRandom simply picks a random index from the array, ensuring uniform randomness.

Seeing the array state makes it clear why random.choice returns any element with equal probability.

Practice

1. You are given a binary array and need to find the length of the longest contiguous subarray with an equal number of 0s and 1s. Which algorithmic approach guarantees an optimal O(n) time solution?

easy

A. Brute force nested loops checking all subarrays for equal 0s and 1s

B. Prefix sum combined with a hash map to track first occurrences of prefix sums

C. Dynamic programming storing counts of 0s and 1s separately for all subarrays

D. Greedy approach expanding subarrays while counts of 0s and 1s remain equal

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the longest contiguous subarray with equal 0s and 1s efficiently.

2. Step 2: Identify algorithmic pattern

   Using prefix sums transformed by treating 0 as -1, and a hash map to store earliest prefix sum indices, allows O(n) time detection of subarrays with zero sum difference.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Prefix sum + hash map is classic for equal 0/1 subarray [OK]

Hint: Prefix sums + hash map track equal 0s and 1s efficiently [OK]

Common Mistakes:

• Thinking greedy can find longest equal 0/1 subarray
• Using DP that tracks counts separately is inefficient
• Brute force is correct but not optimal

2. Given the following code snippet, what is the final output when calling isHappy(7)?

def sum_of_squares(num):
    return sum(int(d) ** 2 for d in str(num))

UNHAPPY_CYCLE = {4, 16, 37, 58, 89, 145, 42, 20}

def isHappy(n: int) -> bool:
    while n != 1 and n not in UNHAPPY_CYCLE:
        n = sum_of_squares(n)
    return n == 1

print(isHappy(7))

easy

A. false

B. true

C. The code runs infinitely

D. Raises a runtime error

Solution

1. Step 1: Trace sum_of_squares for n=7

   7 -> 7² = 49

2. Step 2: Iterate until n=1 or cycle detected

   49 -> 4²+9²=16+81=97 -> 9²+7²=81+49=130 -> 1²+3²+0²=1+9+0=10 -> 1²+0²=1 -> loop ends, returns true

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   7 is a happy number, code returns true [OK]

Hint: Trace sum_of_squares until 1 or cycle [OK]

Common Mistakes:

• Assuming 7 leads to cycle or infinite loop

3. You are given an unsorted array of integers and need to find the length of the longest sequence of consecutive integers that appear in the array. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Use a hash set to store all numbers, then for each number that is the start of a sequence, count consecutive numbers forward.

B. Use dynamic programming to build the longest consecutive subsequence ending at each element.

C. Sort the array and then scan linearly to find the longest consecutive sequence.

D. Use a nested loop to check for consecutive sequences starting from each element.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the longest consecutive sequence in an unsorted array efficiently.

2. Step 2: Evaluate approaches

   Sorting then scanning is O(n log n), nested loops are O(n²), and DP is not straightforward here. Using a hash set to detect sequence starts and count forward achieves O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash set membership checks are O(1), enabling linear time [OK]

Hint: Hash set start detection enables O(n) solution [OK]

Common Mistakes:

• Assuming sorting is optimal enough
• Trying DP which doesn't fit this problem
• Using nested loops leading to O(n²)

4. Suppose the problem is modified so that characters in s can be reused multiple times to map to characters in t (i.e., the mapping is many-to-one, not one-to-one). Which of the following approaches correctly adapts the isomorphic strings check to this new requirement?

hard

A. Use nested loops to check all pairs for consistency as in brute force

B. Keep bidirectional hash maps but allow multiple s chars to map to the same t char

C. Sort both strings and compare if sorted strings are equal

D. Use only a single hash map from s to t without reverse mapping checks

Solution

1. Step 1: Understand the relaxed mapping constraint

   Since multiple characters in s can map to the same character in t, the reverse mapping from t to s is no longer one-to-one and need not be checked.

2. Step 2: Adapt the algorithm

   Using a single hash map from s to t suffices to ensure each s character maps consistently, ignoring reverse mapping.

3. Step 3: Evaluate other options

   Bidirectional maps are unnecessary and would incorrectly reject valid mappings; brute force is inefficient; sorting does not preserve character positions.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Single-direction mapping fits many-to-one mapping requirement [OK]

Hint: Relaxed mapping removes need for reverse checks [OK]

Common Mistakes:

• Keeping bidirectional checks unnecessarily
• Using brute force causing inefficiency
• Sorting strings which breaks order

5. Suppose the problem changes: now elements can be reused multiple times, and you want the top k elements by total frequency including duplicates. Which modification to the optimal bucket sort approach correctly handles this?

hard

A. Use the same bucket sort approach since frequencies already count duplicates.

B. Modify frequency counting to count unique elements only, then apply bucket sort.

C. Use a min-heap to track top k elements dynamically as frequencies update with reuse.

D. Sort the entire nums array and pick the top k elements by frequency.

Solution

1. Step 1: Understand reuse changes frequency dynamics

   Elements can appear multiple times dynamically, so frequencies update continuously.

2. Step 2: Bucket sort is static and cannot handle dynamic frequency updates

   Min-heap allows maintaining top k elements efficiently as frequencies change.

3. Step 3: Choose min-heap approach for dynamic top k tracking

   Min-heap keeps size k and updates with new frequencies, suitable for reuse scenario.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Bucket sort is static; min-heap adapts to frequency changes [OK]

Hint: Dynamic frequency updates require min-heap, not bucket sort [OK]

Common Mistakes:

• Assuming bucket sort works with dynamic reuse
• Counting unique elements only loses frequency info
• Sorting entire array is inefficient