519. Random Flip Matrix Solution & Explanation

Q: Is Random Flip Matrix easy or hard?

Random Flip Matrix is rated Medium on LeetCode but can feel tricky because it combines hashing with randomized algorithms. The challenge is ensuring uniform randomness while preventing duplicate selections without storing the entire matrix.

Q: Random Flip Matrix Python/Java solution

Python and Java implementations typically follow the hash map index-mapping approach. Maintain a dictionary or HashMap, track the remaining cell count, generate a random index, resolve its mapped value, and convert the flattened index to matrix coordinates using division and modulo.

Q: How to solve Random Flip Matrix in O(1)?

Flatten the matrix into a conceptual array of size m*n. Randomly pick an index within the remaining range and use a hash map to map that index to the last available position, mimicking a swap. Decrease the available range after each flip. This ensures each flip executes in constant average time.

Q: What is the best approach for Random Flip Matrix?

The most efficient approach uses a hash map with virtual index swapping. Treat the matrix as a flattened array of size m*n and randomly select indices from a shrinking range. A hash map remaps used indices to remaining ones, simulating a swap. This keeps flip() operations O(1) average time while using only O(k) extra space.

Q: Is Random Flip Matrix asked at Google/Amazon/Meta?

Randomized data structure problems like Random Flip Matrix commonly appear in interviews at companies such as Google, Amazon, and Meta. They test understanding of hashing, random selection, and space optimization under large constraints.

Q: What data structure is used in Random Flip Matrix?

The optimal solution uses a hash table to track remapped indices and simulate swaps without storing the entire matrix. The algorithm also relies on randomized number generation and simple math to convert flattened indices back into row and column coordinates.

Q: What is the time complexity of Random Flip Matrix?

Using the hash map index-mapping technique, each flip() runs in O(1) average time and reset() is O(1) by clearing the map and restoring the range. The Fisher-Yates shuffle approach also provides O(1) per flip but requires O(mn) initialization and storage.

The problem

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.

Example 1:

Input
["Solution", "flip", "flip", "flip", "reset", "flip"]
[[3, 1], [], [], [], [], []]
Output
[null, [1, 0], [2, 0], [0, 0], null, [2, 0]]

Explanation
Solution solution = new Solution(3, 1);
solution.flip();  // return [1, 0], [0,0], [1,0], and [2,0] should be equally likely to be returned.
solution.flip();  // return [2, 0], Since [1,0] was returned, [2,0] and [0,0]
solution.flip();  // return [0, 0], Based on the previously returned indices, only [0,0] can be returned.
solution.reset(); // All the values are reset to 0 and can be returned.
solution.flip();  // return [2, 0], [0,0], [1,0], and [2,0] should be equally likely to be returned.

Constraints:

1 <= m, n <= 10⁴
There will be at least one free cell for each call to flip.
At most 1000 calls will be made to flip and reset.

Approach overview

Problem Overview: You have an m x n matrix initially filled with 0s. Each call to flip() must randomly select a cell containing 0, change it to 1, and return its coordinates. A cell cannot be flipped twice. reset() restores the matrix to all zeros.

Approach 1: Hash Map to Track Flipped Cells (O(1) average time, O(k) space)

This approach treats the matrix as a flattened array of size m * n. Instead of storing the entire matrix, maintain a shrinking range of available indices. When flip() is called, generate a random index within the remaining range. A hash table maps used indices to the last available index, simulating a virtual swap similar to the end of an array. After selecting an index, decrease the available range so the same position cannot be chosen again. Each flip runs in O(1) average time with O(k) space where k is the number of flips. This technique relies on randomized algorithms to ensure uniform selection.

The key insight is avoiding storage of the full matrix. Instead of marking cells, you remap indices dynamically. If a random index was previously swapped, the hash map tells you its current mapped value. This keeps the selection uniform while minimizing memory usage.

Approach 2: Fisher-Yates Shuffle (O(1) per flip after O(mn) setup, O(mn) space)

Another option is to explicitly store all m * n cell indices in a list and apply the Fisher–Yates shuffle idea. Initially fill an array with numbers 0..(m*n-1). Each flip() selects a random index within the remaining range and swaps it with the last unused element. The returned value converts back to matrix coordinates using division and modulo.

This is the classic Fisher-Yates shuffle, commonly used for uniform random permutations. Each flip runs in O(1) time because it performs one random selection and one swap. However, it requires storing the entire array, leading to O(mn) space. For large matrices this can become expensive compared to the hash-map method.

Recommended for interviews: The hash map mapping technique is usually expected. It demonstrates understanding of space optimization and randomized index mapping. The Fisher–Yates approach is conceptually simpler and still correct, but interviewers often prefer the hash-map version because it avoids allocating O(mn) memory while keeping flip() constant time.

Approach 1: Using a Hash Map to Track Flipped Cells

This approach maps the 2D matrix to a 1D space, where each 0 cell is equally likely to be chosen and flipped to 1. It utilizes a hashmap to record changes, associating flipped 1D indices to the cells at the end of the list of available indices, which effectively "shrinks" the pool of zeros.

Python

import random

class Solution:
    def __init__(self, m: int, n: int):
        self.m, self.n = m, n
        self.total = m * n
        self.flipped = {}
        self.available = self.total

    def flip(self) -> [int]:
        x = random.randint(0, self.available - 1)
        self.available -= 1
        idx = self.flipped.get(x, x)
        self.flipped[x] = self.flipped.get(self.available, self.available)
        return divmod(idx, self.n)

    def reset(self) -> None:
        self.flipped.clear()
        self.available = self.total

Java

import java.util.HashMap;
import java.util.Random;

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

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

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

    public void reset() {
        map.clear();
        available = total;
    }
}

using System;
using System.Collections.Generic;

public class Solution {
    private int m, n, total, available;
    private Dictionary<int, int> map;
    private Random rand;

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

    public int[] Flip() {
        int x = rand.Next(available--);
        int idx = map.ContainsKey(x) ? map[x] : x;
        map[x] = map.ContainsKey(available) ? map[available] : available;
        return new int[]{idx / n, idx % n};
    }

    public void Reset() {
        map.Clear();
        available = total;
    }
}

Implementation Explanation:

The class Solution maps a 2D matrix to a 1D array. The constructor initializes the matrix dimensions and calculates the total available slots.
The flip function generates a random index within the range of available slots. It retrieves the corresponding mapped index, decreasing the available slot count to ensure no repeats.
The reset method clears the map and resets the availability to full.

Complexity

Time Complexity: O(1) per flip operation as getting and setting in the hashmap is O(1).
Space Complexity: O(K) where K is the number of flipped cells recorded in the hashmap.

Try this approach in the editor

Approach 2: Using Fisher-Yates Shuffle

The Fisher-Yates shuffle is an algorithm used to generate a random permutation of a finite sequence, ideal for selecting random indices in the given problem. Each matrix cell is represented as a 1D element, and instead of mapping indices to a hashmap, we can shuffle the sequence using Fisher-Yates in a constrained manner to ensure uniform randomness.

C++

#include <vector>
#include <cstdlib>

class Solution {
public:
    Solution(int m, int n) : m(m), n(n), total(m * n), available(total) {
        rng = std::mt19937(rd());
    }
    
    std::vector<int> flip() {
        int x = rng() % available--;
        int idx = map.count(x) ? map[x] : x;
        map[x] = map.count(available) ? map[available] : available;
        return {idx / n, idx % n};
    }
    
    void reset() {
        map.clear();
        available = total;
    }

private:
    int m, n, total, available;
    std::unordered_map<int, int> map;
    std::random_device rd;
    std::mt19937 rng;
};

JavaScript

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

Implementation Explanation:

In this C++ solution, the use of the Fisher-Yates-inspired shuffle allows efficient random index picking by leveraging the mt19937 pseudo-random generator for uniform selection from available indices.
The approach does not use Fisher-Yates in a conventional permuting manner but adopts similar principles for tracking cell states using an indexed map.
The reset function clears tracking structures to revert all flipped states.

Complexity

Time Complexity: O(1) per operation as index tracking uses constant time access.
Space Complexity: O(K) where K is the maximal space occupied by the unordered_map during flip operations.

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using a Hash Map to Track Flipped Cells	Time Complexity: O(1) per flip operation as getting and setting in the hashmap is O(1). Space Complexity: O(K) where K is the number of flipped cells recorded in the hashmap.
Using Fisher-Yates Shuffle	Time Complexity: O(1) per operation as index tracking uses constant time access. Space Complexity: O(K) where K is the maximal space occupied by the unordered_map during flip operations.

Complexity analysis

Approach	Time	Space	When to Use
Hash Map Index Mapping	O(1) average per flip	O(k)	Best general solution when the matrix is large and you want to avoid storing all cells
Fisher-Yates Shuffle	O(1) per flip after O(mn) setup	O(mn)	Simpler implementation when memory is not a constraint

Frequently asked questions

Is Random Flip Matrix easy or hard?

Random Flip Matrix is rated Medium on LeetCode but can feel tricky because it combines hashing with randomized algorithms. The challenge is ensuring uniform randomness while preventing duplicate selections without storing the entire matrix.

Random Flip Matrix Python/Java solution

Python and Java implementations typically follow the hash map index-mapping approach. Maintain a dictionary or HashMap, track the remaining cell count, generate a random index, resolve its mapped value, and convert the flattened index to matrix coordinates using division and modulo.

How to solve Random Flip Matrix in O(1)?

Flatten the matrix into a conceptual array of size m*n. Randomly pick an index within the remaining range and use a hash map to map that index to the last available position, mimicking a swap. Decrease the available range after each flip. This ensures each flip executes in constant average time.

What is the best approach for Random Flip Matrix?

The most efficient approach uses a hash map with virtual index swapping. Treat the matrix as a flattened array of size m*n and randomly select indices from a shrinking range. A hash map remaps used indices to remaining ones, simulating a swap. This keeps flip() operations O(1) average time while using only O(k) extra space.

Is Random Flip Matrix asked at Google/Amazon/Meta?

Randomized data structure problems like Random Flip Matrix commonly appear in interviews at companies such as Google, Amazon, and Meta. They test understanding of hashing, random selection, and space optimization under large constraints.

What data structure is used in Random Flip Matrix?

The optimal solution uses a hash table to track remapped indices and simulate swaps without storing the entire matrix. The algorithm also relies on randomized number generation and simple math to convert flattened indices back into row and column coordinates.

What is the time complexity of Random Flip Matrix?

Using the hash map index-mapping technique, each flip() runs in O(1) average time and reset() is O(1) by clearing the map and restoring the range. The Fisher-Yates shuffle approach also provides O(1) per flip but requires O(mn) initialization and storage.

Random Flip Matrix solution and explanation

The problem

Approach overview

Approach 1: Using a Hash Map to Track Flipped Cells

Approach 2: Using Fisher-Yates Shuffle

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Random Flip Matrix solution and explanation

The problem

Approach overview

Approach 1: Using a Hash Map to Track Flipped Cells

Approach 2: Using Fisher-Yates Shuffle

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems