Random Flip Matrix - Practice Coding Problems

Random Flip Matrix - Problem

You are given an m x n binary grid matrix with all values initially set to 0. Design an algorithm to randomly pick an index (i, j) where matrix[i][j] == 0 and flip it to 1.

All indices (i, j) where matrix[i][j] == 0 should be equally likely to be returned. Optimize your algorithm to minimize the number of calls to the built-in random function and optimize 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] where matrix[i][j] == 0 and flips it to 1
void reset() - Resets all values of the matrix to 0

Input & Output

Example 1 — Basic 2x3 Matrix

$ Input: m = 2, n = 3

› Output: [0,1] (or any valid position)

💡 Note: Initialize 2×3 matrix with all 0s. First flip() call can return any position like [0,1], which gets flipped to 1. Matrix becomes [[0,1,0],[0,0,0]].

Example 2 — Small 1x2 Matrix

$ Input: m = 1, n = 2

› Output: [0,0] or [0,1]

💡 Note: With only 2 positions available, first flip returns either [0,0] or [0,1] with equal probability. Second flip would return the remaining position.

Example 3 — Single Cell Matrix

$ Input: m = 1, n = 1

› Output: [0,0]

💡 Note: Only one position [0,0] available. First flip() must return [0,0]. Any subsequent flip() calls would have no valid positions (in practice, problem guarantees valid calls).

Constraints

1 ≤ m, n ≤ 10⁴
At most 1000 calls will be made to flip and reset
It is guaranteed that there will be at least one free cell for each call to flip

Visualization

Tap to expand

Understanding the Visualization

Initial State

m×n matrix filled with all 0s

Random Selection

Pick random position where matrix[i][j] == 0

Flip Result

Change selected position to 1 and return coordinates

Key Takeaway

🎯 Key Insight: Use Fisher-Yates shuffle to efficiently select from shrinking pool of available positions

Asked in

G Google 25 f Facebook 18 a Amazon 15 M Microsoft 12

The key insight is using Fisher-Yates shuffle technique to efficiently select random positions without gaps. Instead of maintaining a full matrix or list, we use a hash map to track swapped indices. Optimal approach uses hash map with 1D index mapping for O(1) flip operation. Time: O(1), Space: O(k) where k is flipped cells.

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map - Track Available Positions	O(1)	O(m×n)	Maintain a set of all available positions and randomly pick from them
Brute Force - Keep Trying Random Positions	O(1) to O(∞)	O(1)	Repeatedly generate random coordinates until finding an unflipped cell
Fisher-Yates Shuffle with Hash Map	O(1)	O(k)	Map indices to positions and use swap technique to avoid gaps

Hash Map - Track Available Positions — Algorithm Steps

Initialize set with all (i,j) positions
For flip(): randomly pick position from available set
Remove picked position from set and return it
For reset(): restore all positions to available set

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct {
    int m, n;
    int** positions;
    int count;
} Solution;

Solution* createSolution(int m, int n) {
    srand(time(NULL));
    Solution* sol = (Solution*)malloc(sizeof(Solution));
    sol->m = m;
    sol->n = n;
    sol->count = m * n;
    sol->positions = (int**)malloc(sol->count * sizeof(int*));
    int idx = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            sol->positions[idx] = (int*)malloc(2 * sizeof(int));
            sol->positions[idx][0] = i;
            sol->positions[idx][1] = j;
            idx++;
        }
    }
    return sol;
}

int* flip(Solution* sol) {
    int idx = rand() % sol->count;
    int* result = (int*)malloc(2 * sizeof(int));
    result[0] = sol->positions[idx][0];
    result[1] = sol->positions[idx][1];
    
    // Remove by swapping with last element
    int* temp = sol->positions[idx];
    sol->positions[idx] = sol->positions[sol->count - 1];
    sol->positions[sol->count - 1] = temp;
    sol->count--;
    
    return result;
}

void resetSolution(Solution* sol) {
    sol->count = sol->m * sol->n;
    int idx = 0;
    for (int i = 0; i < sol->m; i++) {
        for (int j = 0; j < sol->n; j++) {
            sol->positions[idx][0] = i;
            sol->positions[idx][1] = j;
            idx++;
        }
    }
}

int* solution(int m, int n) {
    Solution* sol = createSolution(m, n);
    return flip(sol);
}

int main() {
    int m, n;
    scanf("%d", &m);
    scanf("%d", &n);
    int* result = solution(m, n);
    printf("[%d,%d]\n", result[0], result[1]);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Random selection from set is O(1), removal is O(1) on average

✓ Linear Growth

Space Complexity

O(m×n)

Store all m×n coordinates in a set or list structure

⚡ Linearithmic Space

32.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen