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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Random Flip Matrix

Difficulty: Medium

Problem Description

There is an m x n binary grid matrix with all the values set to 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.

Key Insights

  • The grid can be represented as a list of available indices.
  • We can use a hash map or dictionary to track the available positions.
  • A random selection should be made from the list of available indices.
  • Flipping an index to 1 means we need to remove it from the list of available indices.
  • Resetting the matrix requires restoring all positions back to 0.

Space and Time Complexity

Time Complexity:

  • flip(): O(1) on average (with random access to the list).
  • reset(): O(n * m) in the worst case (if we reset each position). Space Complexity: O(k) where k is the number of flips (number of indices flipped to 1).

Solution

The solution involves maintaining a list of available indices and a mapping of the grid's dimensions. When we call the flip method, we randomly select an index from the list of available indices, flip that index to 1, and then remove it from the list. The reset method will clear the flips by resetting the entire grid back to 0.

We can also utilize a hash map to ensure that we can efficiently maintain and access the available positions.

Code Solutions

import random

class Solution:

    def __init__(self, m: int, n: int):
        self.m = m
        self.n = n
        self.flipped = set()  # To keep track of flipped positions
        self.total_cells = m * n

    def flip(self) -> List[int]:
        # Get a random index that hasn't been flipped
        idx = random.randint(0, self.total_cells - 1)
        while idx in self.flipped:
            idx = random.randint(0, self.total_cells - 1)

        self.flipped.add(idx)  # Mark this index as flipped
        return [idx // self.n, idx % self.n]  # Convert to (i, j)

    def reset(self) -> None:
        self.flipped.clear()  # Clear the flipped positions
← Back to All Questions