Problem Description

You have an m x n binary grid (matrix) where all values start as 0. Your task is to implement a class that can:

1. Randomly select and flip zeros to ones: Pick a random cell that contains 0 and change it to 1. Each cell with value 0 should have an equal probability of being selected.

2. Reset the grid: Change all values back to 0.

The class should have three methods:

• Solution(int m, int n): Initialize with grid dimensions m rows and n columns
• int[] flip(): Return coordinates [i, j] of a randomly selected cell where matrix[i][j] == 0, then set that cell to 1
• void reset(): Set all cells back to 0

Key Requirements:

• Each call to flip() must return a uniformly random cell that currently contains 0
• Once a cell is flipped to 1, it cannot be selected again until reset() is called
• The algorithm should minimize calls to the built-in random function
• Optimize for time and space complexity

Example Usage:

obj = Solution(3, 2)  # Create a 3x2 grid of zeros
coord1 = obj.flip()   # Returns random [i,j] where matrix[i][j] was 0, sets it to 1
coord2 = obj.flip()   # Returns different random [i,j] where matrix[i][j] was 0, sets it to 1
obj.reset()           # All cells back to 0
coord3 = obj.flip()   # Can now return any [i,j] again since all are 0

The challenge is efficiently tracking which cells have been flipped without maintaining the entire matrix in memory, especially for large grids where most cells remain 0.

Intuition

The naive approach would be to maintain the entire m x n matrix and track which cells are flipped. However, for large matrices where we only flip a few cells, this wastes memory storing mostly zeros.

Let's think differently. Instead of tracking which cells are 1, we can work with indices. Initially, we have m * n cells, all containing 0. We can map each cell (i, j) to a single index using the formula: index = i * n + j.

Now imagine we have indices from 0 to total-1 (where total = m * n). When we need to flip a cell:

1. Pick a random number from 0 to total-1
2. Flip that cell
3. Reduce our available range by 1

But here's the problem: how do we avoid picking the same cell twice? We need to "remove" the already-flipped index from our selection pool.

This is where the key insight comes in - we can use a virtual array swapping technique. Think of it like picking cards from a deck:

• When you pick a card, you don't want to pick it again
• One way is to swap the picked card with the last card in the deck
• Then reduce the deck size by 1
• Next time, you only pick from the remaining cards

We can simulate this without actually maintaining an array! We use a hashmap to track only the swaps:

• Start with virtual array [0, 1, 2, ..., total-1]
• When we pick index x, we swap it with the last element (at position total-1)
• Store this swap in our hashmap: mp[x] = value_at_last_position
• Decrease total by 1

The beauty is that most positions keep their default values (position i has value i), so we only store the exceptions in our hashmap. When looking up a position, if it's not in the hashmap, we know it hasn't been swapped and still holds its original value.

This gives us O(1) time per flip with only O(k) space where k is the number of flips performed, rather than O(m*n) space for the entire matrix.

Learn more about Math patterns.

Solution Approach

Let's implement the virtual array swapping technique step by step:

Data Structures

• self.m, self.n: Store grid dimensions
• self.total: Track the number of unflipped cells (initially m * n)
• self.mp: HashMap to store the swapped values

Implementation Details

Initialization (__init__)

def __init__(self, m: int, n: int):
    self.m = m
    self.n = n
    self.total = m * n
    self.mp = {}

We start with total = m * n unflipped cells and an empty hashmap.

Flip Operation (flip)

def flip(self) -> List[int]:
    self.total -= 1
    x = random.randint(0, self.total)
    idx = self.mp.get(x, x)
    self.mp[x] = self.mp.get(self.total, self.total)
    return [idx // self.n, idx % self.n]

Let's trace through this:

1. self.total -= 1: Decrement first, so total now represents the last valid index
2. x = random.randint(0, self.total): Pick random index from [0, total] inclusive
3. idx = self.mp.get(x, x): Get the actual value at position x
   • If x is in hashmap, use the swapped value
   • Otherwise, the value at position x is just x itself
4. self.mp[x] = self.mp.get(self.total, self.total): Swap with last element
   • Get value at position total (either from hashmap or default total)
   • Store it at position x
5. Convert linear index back to 2D coordinates: [idx // n, idx % n]

Example Walkthrough: Consider a 2×3 grid (6 cells total):

• Virtual array: [0, 1, 2, 3, 4, 5], total = 6

First flip:

• total becomes 5
• Random pick: say x = 2
• idx = 2 (not in hashmap yet)
• mp[2] = 5 (swap position 2 with position 5)
• Return [2//3, 2%3] = [0, 2]
• Virtual array now: [0, 1, 5, 3, 4, 2] (only mp = {2: 5} stored)

Second flip:

• total becomes 4
• Random pick: say x = 2 again
• idx = mp[2] = 5 (use swapped value)
• mp[2] = 4 (swap with new last element)
• Return [5//3, 5%3] = [1, 2]
• Virtual array now: [0, 1, 4, 3, 5, 2] (only mp = {2: 4} stored)

Reset Operation (reset)

def reset(self) -> None:
    self.total = self.m * self.n
    self.mp.clear()

Simply restore total to original size and clear the hashmap.

Complexity Analysis

• Time Complexity: O(1) for both flip() and reset()
• Space Complexity: O(k) where k is the number of flips performed
• Random calls: Only one random number generation per flip

Example Walkthrough

Let's walk through a concrete example with a 2×2 grid (4 cells total) to illustrate how the virtual array swapping technique works:

Initial Setup:

• Grid dimensions: 2×2
• Total cells: 4
• Virtual array conceptually: [0, 1, 2, 3] (representing cells (0,0), (0,1), (1,0), (1,1))
• HashMap: empty {}

First flip():

1. Decrement total: total = 3 (last valid index is now 3)
2. Random pick: suppose we get x = 1
3. Look up actual value at position 1: idx = mp.get(1, 1) = 1 (not in map, so use default)
4. Swap position 1 with position 3: mp[1] = mp.get(3, 3) = 3
5. Convert index 1 to coordinates: [1//2, 1%2] = [0, 1]
6. Return [0, 1] - cell at row 0, column 1 is flipped

State after first flip:

• Virtual array conceptually: [0, 3, 2, 1]
• HashMap: {1: 3}
• Available range: indices 0-2

Second flip():

1. Decrement total: total = 2
2. Random pick: suppose we get x = 1 again
3. Look up actual value: idx = mp.get(1, 1) = 3 (found in map!)
4. Swap position 1 with position 2: mp[1] = mp.get(2, 2) = 2
5. Convert index 3 to coordinates: [3//2, 3%2] = [1, 1]
6. Return [1, 1] - cell at row 1, column 1 is flipped

State after second flip:

• Virtual array conceptually: [0, 2, 3, 1]
• HashMap: {1: 2}
• Available range: indices 0-1

Third flip():

1. Decrement total: total = 1
2. Random pick: suppose we get x = 0
3. Look up actual value: idx = mp.get(0, 0) = 0 (not in map)
4. Swap position 0 with position 1: mp[0] = mp.get(1, 1) = 2 (use mapped value!)
5. Convert index 0 to coordinates: [0//2, 0%2] = [0, 0]
6. Return [0, 0] - cell at row 0, column 0 is flipped

State after third flip:

• HashMap: {1: 2, 0: 2}
• Available range: index 0 only

reset():

• Set total = 4
• Clear hashmap: mp = {}
• All cells are available again

The key insight is that we only store the "exceptions" in our hashmap - positions that have been swapped. Most positions still hold their default values, saving significant memory for large grids with few flips.

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__(m, n): O(1) - Simple variable initialization
• flip(): O(1) - All operations (random number generation, dictionary get/set operations, arithmetic operations) take constant time
• reset(): O(k) where k is the number of flipped cells stored in the dictionary at the time of reset. In the worst case, this could be O(m * n) if all cells have been flipped

Space Complexity:

• Overall space: O(k) where k is the number of flipped cells
• In the worst case: O(m * n) when all cells have been flipped before a reset
• The dictionary mp stores at most one entry per flip operation, mapping indices to avoid repetition
• Additional space: O(1) for storing m, n, and total variables

The algorithm uses Fisher-Yates shuffle technique with a virtual array approach. Instead of maintaining an actual array of size m * n, it uses a dictionary to store only the swapped positions, making it space-efficient for sparse flips.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Random Range

Pitfall: Using random.randint(0, self.total - 1) after decrementing total, or forgetting that random.randint is inclusive on both ends.

# WRONG - This creates off-by-one error
def flip(self) -> List[int]:
    self.total -= 1
    x = random.randint(0, self.total - 1)  # Bug: double subtraction!
    # ...

Why it's wrong: After self.total -= 1, the valid indices are [0, total] inclusive. Using self.total - 1 would miss the last valid index.

Solution: Use random.randint(0, self.total) after decrementing, or use random.randrange(0, self.total) before decrementing.

# CORRECT - Option 1: Decrement first, then use inclusive range
def flip(self) -> List[int]:
    self.total -= 1
    x = random.randint(0, self.total)  # Correct: [0, total] inclusive
    # ...

# CORRECT - Option 2: Use randrange before decrementing
def flip(self) -> List[int]:
    x = random.randrange(0, self.total)  # [0, total) exclusive upper bound
    self.total -= 1
    # ...

2. Incorrect Order of Operations When Swapping

Pitfall: Getting the value at self.total before decrementing it, leading to accessing out-of-bounds indices.

# WRONG - Accessing wrong index for swap
def flip(self) -> List[int]:
    x = random.randint(0, self.total - 1)
    idx = self.mp.get(x, x)
    self.mp[x] = self.mp.get(self.total, self.total)  # Bug: total not decremented yet!
    self.total -= 1
    return [idx // self.n, idx % self.n]

Why it's wrong: If we haven't decremented total yet, self.total points beyond the last valid unflipped cell.

Solution: Always decrement total first to make it point to the last valid index.

3. Memory Leak from Not Cleaning Up HashMap

Pitfall: Storing unnecessary mappings that point to themselves, causing the hashmap to grow unnecessarily.

# INEFFICIENT - Stores redundant mappings
def flip(self) -> List[int]:
    self.total -= 1
    x = random.randint(0, self.total)
    idx = self.mp.get(x, x)
    # Always storing, even when unnecessary
    self.mp[x] = self.mp.get(self.total, self.total)
    self.mp[self.total] = idx  # Bug: Unnecessary reverse mapping!
    return [idx // self.n, idx % self.n]

Why it's wrong: We only need to track positions that have been swapped. Storing identity mappings (where mp[i] = i) wastes space.

Solution: Only store mappings when values differ from their indices. Optionally, clean up mappings that become identity mappings.

# OPTIMIZED - Only store necessary mappings
def flip(self) -> List[int]:
    self.total -= 1
    x = random.randint(0, self.total)
    idx = self.mp.get(x, x)
    last_val = self.mp.get(self.total, self.total)
  
    # Only store if the mapping is meaningful
    if last_val != x:
        self.mp[x] = last_val
    # Optionally remove the used position from map
    self.mp.pop(self.total, None)
  
    return [idx // self.n, idx % self.n]

4. Integer Division Error in Coordinate Conversion

Pitfall: Using the wrong dimension for row/column calculation.

# WRONG - Swapped row/column calculation
def flip(self) -> List[int]:
    # ...
    return [idx % self.n, idx // self.n]  # Bug: row and column swapped!

# OR

# WRONG - Using wrong dimension
def flip(self) -> List[int]:
    # ...
    return [idx // self.m, idx % self.m]  # Bug: should use self.n!

Why it's wrong: In row-major order, we traverse columns first. For an index in a grid with n columns:

• Row = index // n (how many complete rows we've passed)
• Column = index % n (position within current row)

Solution: Always use [idx // self.n, idx % self.n] for row-major order conversion.