We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Random Flip Matrix

Number: 913

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an m x n binary matrix with all entries initially 0, design an algorithm to randomly flip one of the 0s to 1 such that all 0s are equally likely to be chosen. Implement the following operations:

  • Constructor(m, n): Initialize the matrix dimensions.
  • flip(): Randomly pick a 0, flip it to 1 and return its [row, col] index.
  • reset(): Reset the matrix so that all values are 0.

Key Insights

  • Flatten the 2D matrix into a 1D array to simplify random index selection.
  • Use a hash map to perform a "swap" mapping technique to record which indices have been flipped.
  • Each flip reduces the effective size of the available pool, and the mapping allows O(1) operations.
  • The reset operation simply clears the mapping and resets the count.

Space and Time Complexity

Time Complexity: O(1) average per flip call. Space Complexity: O(k) extra space, where k is the number of flips done (at most m*n in the worst-case scenario, but typically much smaller).

Solution

We simulate a random selection from the flattened version of the 2D grid. Consider all cells labeled from 0 to m*n - 1. For each flip, randomly choose an index in this range. Use a hash map to store a "swapped" location if an index has been picked before, effectively reducing the candidate pool. This approach ensures each chosen 0 is uniformly random. When a cell is flipped, the mapping is updated by swapping the chosen cell with the last available cell. The reset operation clears the mapping and resets the available count.

Code Solutions

import random

class Solution:
    def __init__(self, m: int, n: int):
        # Initialize number of rows, columns and the total cell count
        self.m = m
        self.n = n
        self.total = m * n
        # Map to keep track of swapped indices
        self.swapped = {}
        # current available cells
        self.remaining = self.total

    def flip(self) -> [int, int]:
        # Randomly choose an index from available pool [0, remaining - 1]
        rand_idx = random.randint(0, self.remaining - 1)
        # Get the real index using our mapping dictionary
        real_idx = self.swapped.get(rand_idx, rand_idx)
        # Update the chosen spot with the last available cell mapping
        self.remaining -= 1
        # Map the random index to the last cell if exists
        self.swapped[rand_idx] = self.swapped.get(self.remaining, self.remaining)
        # Convert the 1D index back to 2D coordinates
        return [real_idx // self.n, real_idx % self.n]

    def reset(self) -> None:
        # Reset the mapping and available cell count
        self.swapped.clear()
        self.remaining = self.total
← Back to All Questions