Random Flip Matrix

Medium

Asked by:

8 views

Topics:

Arrays

There is an m x n binary grid matrix with all the values set 0 initially. Design an algorithm to randomly pick an index (i, j) where matrix[i][j] == 0 and flips it to 1. All the indices (i, j) where matrix[i][j] == 0 should be equally likely to be returned.

Optimize your algorithm to minimize the number of calls made to the built-in random function of your language and optimize the time and space complexity.

Implement the Solution class:

Solution(int m, int n) Initializes the object with the size of the binary matrix m and n.
int[] flip() Returns a random index [i, j] of the matrix where matrix[i][j] == 0 and flips it to 1.
void reset() Resets all the values of the matrix to be 0.

Example 1:

Input
["Solution", "flip", "flip", "flip", "reset", "flip"]
[[3, 1], [], [], [], [], []]
Output
[null, [1, 0], [2, 0], [0, 0], null, [2, 0]]

Explanation
Solution solution = new Solution(3, 1);
solution.flip();  // return [1, 0], [0,0], [1,0], and [2,0] should be equally likely to be returned.
solution.flip();  // return [2, 0], Since [1,0] was returned, [2,0] and [0,0]
solution.flip();  // return [0, 0], Based on the previously returned indices, only [0,0] can be returned.
solution.reset(); // All the values are reset to 0 and can be returned.
solution.flip();  // return [2, 0], [0,0], [1,0], and [2,0] should be equally likely to be returned.

Constraints:

1 <= m, n <= 10⁴
There will be at least one free cell for each call to flip.
At most 1000 calls will be made to flip and reset.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the matrix (number of rows and columns), and what is the maximum size I should expect for each dimension?
Is the initial matrix guaranteed to be all zeros?
After flipping a cell, will `reset()` ever be called, and if so, how often relative to the number of `flip()` operations?
If `flip()` is called when there are no more zeros in the matrix, what should I return?
Are the row and column indices 0-based or 1-based?

Brute Force Solution

Approach

The brute force approach to this problem is like randomly picking a spot in the matrix, checking if it's already been flipped, and repeating until we find an unflipped spot. We essentially simulate many random coin flips until we get the desired outcome.

Here's how the algorithm would work step-by-step:

Imagine the matrix is a grid of coins, all showing tails.
To 'flip' a coin, we want to change one from tails to heads.
Pick a coin in the grid completely at random.
Check if that coin is currently showing tails. If it's already heads, we made a bad random pick.
If the coin shows tails, flip it to heads. Then, we're done with this flip request.
If the coin was already heads, pick another random coin and repeat the checking process until we find a tails coin.
For the 'reset' functionality, simply change all coins back to tails.

Code Implementation

import random

class RandomFlipMatrix:
    def __init__(self, rows, columns):
        self.rows = rows
        self.columns = columns
        self.matrix = [[0] * columns for _ in range(rows)]
        self.total_cells = rows * columns

    def flip(self):
        # Iterate until we successfully flip an un-flipped cell
        while True:
            random_row = random.randint(0, self.rows - 1)
            random_column = random.randint(0, self.columns - 1)

            # Only flip if the cell is currently 0 (unflipped)
            if self.matrix[random_row][random_column] == 0:
                self.matrix[random_row][random_column] = 1

                # Return the coordinates of the flipped cell
                return [random_row, random_column]

    def reset(self):
        # Reset all cells to 0 (unflipped)
        self.matrix = [[0] * self.columns for _ in range(self.rows)]

Big(O) Analysis

Time Complexity

O(m * n) – The brute force approach involves repeatedly picking random cells until an unflipped cell is found. In the worst-case scenario, where the matrix is nearly full of flipped cells, we might have to try many random cells before finding one that's unflipped. The probability of finding an unflipped cell decreases as more cells are flipped. In the extreme case, when only one cell is unflipped, the expected number of attempts to find it becomes close to m * n. Thus, flipping a single cell can take O(m * n) time in the worst case, where m and n are the dimensions of the matrix. Since the maximum number of flips is also m*n, the reset function takes O(1) time since we just reset all flips.

Space Complexity

O(1) – The provided solution involves repeatedly picking random spots in the matrix without storing any additional information about previously flipped spots or the entire matrix state (other than the inherent matrix itself, which we do not count towards auxiliary space). The 'reset' operation doesn't require any extra data structures either. Therefore, the auxiliary space used is constant, independent of the matrix dimensions. No temporary lists, hash maps, or recursion are used, resulting in O(1) space complexity.

Optimal Solution

Approach

The efficient solution avoids directly representing the entire matrix. It maintains a mapping to simulate flipping elements without having to touch every single cell, making the process much faster especially when the matrix is huge and sparsely flipped.

Here's how the algorithm would work step-by-step:

Imagine the matrix is one long list of cells, numbered sequentially.
When asked to flip a random cell, pick a random number within the bounds of this list.
Check if the cell associated with this number has already been flipped. We can do this using a mapping to store previously flipped cells.
If the cell has been flipped, find what cell it was swapped with earlier (from our mapping).
If the cell hasn't been flipped, note the value associated to that number.
Now, 'flip' it. This really means swapping the random number with the last unflipped cell in the 'list'. Update your mapping with the 'flipped' number pointing to the original content of the last cell.
Decrement the size of the 'list' of available cells to represent that the last cell is no longer available to pick from (it's been flipped).
Return the coordinates of the flipped cell that was requested, translating it from the 'list' index back into row and column numbers.

Code Implementation

import random

class Solution:

    def __init__(self, number_of_rows: int, number_of_columns: int):
        self.number_of_rows = number_of_rows
        self.number_of_columns = number_of_columns
        self.total_cells = number_of_rows * number_of_columns
        self.flipped_cells = {}

    def flip(self) -> list[int]:
        # Generate a random index within the range of available cells.
        random_index = random.randrange(self.total_cells)

        # Check if the random index has been flipped before.
        if random_index in self.flipped_cells:
            result = self.flipped_cells[random_index]
        else:
            result = random_index

        # Get the value of the last available cell.
        if self.total_cells - 1 in self.flipped_cells:
            last_cell_value = self.flipped_cells[self.total_cells - 1]
        else:
            last_cell_value = self.total_cells - 1

        # Update the flipped cells mapping. This is the core 'flip' operation.
        self.flipped_cells[random_index] = last_cell_value

        self.total_cells -= 1

        row_index = result // self.number_of_columns
        column_index = result % self.number_of_columns

        return [row_index, column_index]

    def reset(self) -> None:
        self.total_cells = self.number_of_rows * self.number_of_columns
        self.flipped_cells = {}

Big(O) Analysis

Time Complexity

O(1) – The solution's time complexity is dominated by the hash map operations for checking and updating flipped cells. The getRandom call and the coordinate calculation are O(1). Because hash map lookups and insertions (or updates) take constant time on average, the overall complexity for the flip operation is O(1). Therefore, each call to flip at most touches the hashmap once, so the average time complexity is constant.

Space Complexity

O(F) – The described solution uses a hash map (or dictionary) to store the mapping of flipped indices. In the worst-case scenario, where we flip almost all the cells, the size of this hash map could grow proportionally to the number of flips, denoted as F, where F is the number of times the flip function is called. Therefore, the auxiliary space required is proportional to the number of flips, and since it's the dominant factor, the space complexity is O(F). N, in this context, would represent the total number of cells in the matrix (rows * cols) which is indirectly related to how many flips are possible.

Edge Cases

Case	How to Handle
m or n is zero	Return immediately if m or n is zero as no flips are possible.
m * n is 1	Initialize the data structure and flip the single cell, ensuring getRandom returns only that cell.
m * n exceeds the maximum integer value	Use long or appropriate data type to represent the total number of cells to avoid overflow when calculating random indices.
Repeated calls to flip eventually exhaust all possible flips	Ensure the reservoir/hashmap shrinks and getRandom correctly handles the diminishing range of available indices, halting when no more flips are possible.
Extremely large matrix dimensions (large m * n), causing memory issues	Use a lazy swapping approach (hash map) to store only flipped indices instead of a full matrix representation to conserve memory.
getRandom is called more times than m * n	Ensure flip operations do not access invalid memory and that has been reset will return empty after all positions have been flipped.
The coordinate representation leads to out-of-bounds access.	Ensure modulo operations map to valid row and column indices within the matrix dimensions.
Random number generator returns the same sequence repeatedly.	Use a good quality random number generator with sufficient entropy to provide uniform distribution of flips.

m or n is zero

How to Handle:

Return immediately if m or n is zero as no flips are possible.

m * n is 1

How to Handle:

Initialize the data structure and flip the single cell, ensuring getRandom returns only that cell.

m * n exceeds the maximum integer value

How to Handle:

Use long or appropriate data type to represent the total number of cells to avoid overflow when calculating random indices.

Repeated calls to flip eventually exhaust all possible flips

How to Handle:

Ensure the reservoir/hashmap shrinks and getRandom correctly handles the diminishing range of available indices, halting when no more flips are possible.

Extremely large matrix dimensions (large m * n), causing memory issues

How to Handle:

Use a lazy swapping approach (hash map) to store only flipped indices instead of a full matrix representation to conserve memory.

getRandom is called more times than m * n

How to Handle:

Ensure flip operations do not access invalid memory and that has been reset will return empty after all positions have been flipped.

The coordinate representation leads to out-of-bounds access.

How to Handle:

Ensure modulo operations map to valid row and column indices within the matrix dimensions.

Random number generator returns the same sequence repeatedly.

How to Handle:

Use a good quality random number generator with sufficient entropy to provide uniform distribution of flips.