Random Flip Matrix

medium hash map math design randomized

Problem

Implement flip()/reset() for an m×n matrix of zeros: flip turns one uniformly-random remaining 0 into 1 and returns its (i, j).

Inputm=2, n=3 then flip(), flip(), flip(), flip()

Outputfour distinct (i, j) cells

Remap pick to an unused index via a hash map; uses O(flipped) memory.

flips

import random
class Solution:
    def __init__(self, m, n):
        self.m, self.n = m, n
        self.total = m * n
        self.map = {}
    def flip(self):
        r = random.randrange(self.total)
        self.total -= 1
        x = self.map.get(r, r)
        self.map[r] = self.map.get(self.total, self.total)
        return [x // self.n, x % self.n]
    def reset(self):
        self.total = self.m * self.n
        self.map.clear()

class Solution {
  constructor(m, n) { this.m = m; this.n = n; this.total = m * n; this.map = new Map(); }
  flip() {
    const r = Math.floor(Math.random() * this.total);
    this.total--;
    const x = this.map.get(r) ?? r;
    this.map.set(r, this.map.get(this.total) ?? this.total);
    return [Math.floor(x / this.n), x % this.n];
  }
  reset() { this.total = this.m * this.n; this.map.clear(); }
}

class Solution {
    int m, n, total;
    Map map = new HashMap<>();
    Random rnd = new Random();
    public Solution(int m, int n) { this.m = m; this.n = n; total = m * n; }
    public int[] flip() {
        int r = rnd.nextInt(total--);
        int x = map.getOrDefault(r, r);
        map.put(r, map.getOrDefault(total, total));
        return new int[]{ x / n, x % n };
    }
    public void reset() { total = m * n; map.clear(); }
}

class Solution {
    int m, n, total;
    unordered_map mp;
public:
    Solution(int m, int n) : m(m), n(n), total(m * n) {}
    vector flip() {
        int r = rand() % total--;
        int x = mp.count(r) ? mp[r] : r;
        mp[r] = mp.count(total) ? mp[total] : total;
        return { x / n, x % n };
    }
    void reset() { total = m * n; mp.clear(); }
};

Explanation

We need to pick a random still-zero cell each time, without ever repeating, and without wasting memory on a huge matrix. The trick is to treat the matrix as a flat list of m*n indices and run one step of the Fisher-Yates shuffle, but store only the cells we have touched in a hash map.

The variable total counts how many cells are still unused. To flip, we pick a random index r in [0, total), decrement total, and then figure out the real cell behind r: x = map.get(r, r) — if r was remapped earlier we use that, otherwise r itself.

Then we "remove" x from the pool by pointing map[r] at whatever currently sits in the last live slot total (again via map.get(total, total)). This is the classic swap-with-the-end move, but recorded sparsely so untouched slots cost nothing. Finally we convert the flat index back to coordinates with [x // n, x % n].

Example: a 2×3 matrix has 6 cells. Say the first flip picks r = 4; we return cell (1, 1) and remap index 4 to point at the value at slot 5, shrinking the live range. A later pick of 4 now lands on that swapped-in value instead, so we never return the same cell twice.

Each flip is a couple of map operations, so O(1) time, and memory grows only with the number of flips, not the matrix size.

Time: O(1) per flip Space: O(flipped)