Random flip matrix

Hash Table Math Reservoir Sampling Randomized

45.4% acceptance

Feb 19, 2026

461

135

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

* impl Solution {

 *     fn new(m: i32, n: i32) -> Self {

 *     }

 *     fn flip(&self) -> Vec<i32> {

 *     }

 *     fn reset(&self) {

 *     }
 * }
 */

/**
 * Your Solution object will be instantiated and called as such:
 * let obj = Solution::new(m, n);
 * let ret_1: Vec<i32> = obj.flip();
 * obj.reset();
 */

use std::collections::HashMap;
use rand::Rng;
struct Solution {
  m: i32,
  n: i32,
  total: i32,
  map: HashMap<i32, i32>,
}
impl Solution {
  fn new(m: i32, n: i32) -> Self {
    Solution { m, n, total: m * n, map: HashMap::new() }
  }
  fn flip(&mut self) -> Vec<i32> {
    let mut rng = rand::rng();
    let r = rng.random_range(0..self.total);
    self.total -= 1;
    let idx = *self.map.get(&r).unwrap_or(&r);
    let last = *self.map.get(&self.total).unwrap_or(&self.total);
    self.map.insert(r, last);
    vec![idx / self.n, idx % self.n]
  }
  fn reset(&mut self) {
    self.total = self.m * self.n;
    self.map.clear();
  }
}