Code Implementation

import random

class Solution:

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

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

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

#include <unordered_map>
#include <vector>
#include <cstdlib>

class Solution {
    int m, n, total;
    std::unordered_map<int, int> map;
public:
    Solution(int m, int n) : m(m), n(n), total(m * n) {}

    std::vector<int> flip() {
        int x = rand() % total;
        --total;
        int idx = map.count(x) ? map[x] : x;
        map[x] = map.count(total) ? map[total] : total;
        return {idx / n, idx % n};
    }

    void reset() {
        total = m * n;
        map.clear();
    }
};
      

import java.util.*;

class Solution {
    private int m, n, total;
    private Map<Integer, Integer> map;
    private Random rand;

    public Solution(int m, int n) {
        this.m = m;
        this.n = n;
        this.total = m * n;
        this.map = new HashMap<>();
        this.rand = new Random();
    }

    public int[] flip() {
        int x = rand.nextInt(total);
        total--;
        int idx = map.getOrDefault(x, x);
        map.put(x, map.getOrDefault(total, total));
        return new int[]{idx / n, idx % n};
    }

    public void reset() {
        total = m * n;
        map.clear();
    }
}
      

var Solution = function(m, n) {
    this.m = m;
    this.n = n;
    this.total = m * n;
    this.map = new Map();
};

Solution.prototype.flip = function() {
    let x = Math.floor(Math.random() * this.total);
    this.total--;
    let idx = this.map.has(x) ? this.map.get(x) : x;
    this.map.set(x, this.map.has(this.total) ? this.map.get(this.total) : this.total);
    return [Math.floor(idx / this.n), idx % this.n];
};

Solution.prototype.reset = function() {
    this.total = this.m * this.n;
    this.map.clear();
};
      

Problem Description

The Random Flip Matrix problem asks us to design a class to randomly flip 0s to 1s in a 2D binary matrix of size m x n. Initially, all values in the matrix are 0. Each call to flip() must randomly select a cell that is currently 0, change it to 1, and return its coordinates. Each 0 cell should have an equal chance of being picked, and no cell should be flipped twice until the matrix is reset. The reset() function should set all cells back to 0.

Key constraints:

• Each cell must be flipped only once until reset.
• Each flip must be uniformly random among all available 0 cells.
• Efficient time and space usage is required due to potentially large matrix sizes.

Thought Process

At first glance, the problem might suggest using a 2D array to track which cells have been flipped. For each flip(), we could generate random coordinates and check if the cell is 0, repeating until we find one. However, this brute-force approach becomes extremely slow as more cells are flipped, since the number of available 0s shrinks over time, leading to many wasted random attempts.

We need a way to efficiently pick an unflipped cell at random and mark it as flipped, without having to scan the entire matrix or retry random picks. This leads to the idea of mapping the 2D matrix into a 1D array and simulating a shuffle, so that each cell is picked exactly once in a random order, much like drawing cards from a deck.

Solution Approach

To solve the problem efficiently, we use a mapping approach inspired by the Fisher-Yates shuffle:

• Flatten the matrix: Treat the m x n matrix as a 1D array of size m * n. Each cell can be represented by a single integer index.
• Simulate random draws: Start with a "deck" of all cell indices. When we flip a cell, we pick a random index x from the remaining unflipped cells (from 0 to total - 1), where total is the number of unflipped cells left.
• Maintain a mapping: To avoid using an actual array of size m * n, we use a hash map to record swaps. After selecting index x, we swap it with the last available index (total - 1) and decrement total.
• Coordinate conversion: To get the 2D coordinates, convert the 1D index back using row = idx // n and col = idx % n.
• Reset: To reset the matrix, just reset total and clear the mapping.

This approach ensures each cell is picked once, and each pick is uniform and efficient, with both flip() and reset() running in expected O(1) time.

Example Walkthrough

Let's walk through an example with m = 2 and n = 3 (a 2x3 matrix):

• Initial matrix (all zeros):
  [0, 0, 0]
  [0, 0, 0]
• First flip():
  - total = 6, pick random x in [0, 5], say x = 2.
  - Map 2D: [0,2] (row 0, col 2).
  - Swap index 2 with 5 (if needed), decrement total to 5.
• Second flip():
  - total = 5, pick random x in [0, 4], say x = 1.
  - Map: [0,1].
  - Swap index 1 with 4, decrement total to 4.
• Continue flipping until all cells are flipped.
  - Each time, the range shrinks and picked indices are "removed" from the pool.
• reset():
  - total back to 6, mapping cleared, all cells are available again.

At no point do we need to store the entire matrix, and every flip is random among remaining 0s.

Time and Space Complexity

• Brute-force:
  • Time: O(1) for reset, but O(m*n) per flip as the matrix fills (due to repeated random picks for finding a 0).
  • Space: O(m*n) for the matrix.
• Optimized mapping approach:
  • Time: O(1) expected per flip() and reset(), since all operations are hash map lookups/updates.
  • Space: O(k), where k is the number of flips since the map only stores swapped indices, never more than m*n.

The optimized approach is both time and space efficient, making it practical for large matrices.

Summary

The Random Flip Matrix problem is elegantly solved by simulating a shuffle over a flattened matrix, using a hash map to track swapped indices. This ensures each cell is flipped exactly once per reset, with uniform randomness and high efficiency. The key insight is to avoid repeated random guessing or storing the entire matrix, and instead use a clever mapping to simulate the process with minimal space and constant time operations.