Problem Description

-519. Random Flip Matrix

The "Random Flip Matrix" problem requires implementing a class that can randomly flip cells in an m×n binary matrix from 0 to 1. The class should support two operations:

Operations:

• flip(): Randomly select a cell that is currently 0, flip it to 1, and return its coordinates [row, col]
• reset(): Reset all cells back to 0 (allowing them to be flipped again)

Constraints:

• All cells start as 0
• flip() should only return coordinates of cells that are currently 0
• Each call to flip() should return a different cell until all cells are flipped
• After reset(), all cells become available for flipping again

Expected Behavior:

• Random selection with uniform probability
• No duplicate coordinates until reset() is called
• Efficient handling of large matrices

Algorithm Walkthrough

⚠️ Issue with Provided Code: The given solution has a fundamental flaw - it returns coordinates sequentially rather than randomly, which violates the problem requirements.

Problems with Current Implementation:

1. Not Random: Always returns cells in sequential order (0,0) → (0,1) → ... → (m-1,n-1)
2. No Tracking: Doesn't track which cells have been flipped
3. Incorrect Reset: reset() method is empty and doesn't reset the position

Correct Algorithm Approaches:

Approach 1: HashSet Tracking

• Use a HashSet to track flipped positions
• Generate random coordinates until finding an unflipped cell
• Becomes inefficient as matrix fills up

Approach 2: Fisher-Yates Shuffle (Optimal)

• Map 2D coordinates to 1D indices: index = row * n + col
• Use a HashMap to simulate array swapping without actual array
• When selecting index i, swap with a random index from remaining positions
• This ensures O(1) random selection without duplicates

Fisher-Yates Implementation:

// Map stores swapped values: map[i] = j means position i contains value j
HashMap<Integer, Integer> map = new HashMap<>();
int total = m * n;  // Total positions
int remaining = total;  // Remaining unflipped positions

public int[] flip() {
    Random rand = new Random();
    int randomIndex = rand.nextInt(remaining);

    // Get actual value at randomIndex (accounting for swaps)
    int actualValue = map.getOrDefault(randomIndex, randomIndex);

    // Swap with last unflipped position
    int lastIndex = remaining - 1;
    map.put(randomIndex, map.getOrDefault(lastIndex, lastIndex));

    remaining--;

    // Convert 1D index back to 2D coordinates
    return new int[]{actualValue / n, actualValue % n};
}

Complexity Analysis

Current (Incorrect) Implementation:

• Time: O(1) for both operations
• Space: O(1)
• Problem: Not random, doesn't meet requirements

Correct Fisher-Yates Implementation:

• Time:
  • flip(): O(1) average case
  • reset(): O(1)
• Space: O(k) where k is number of flips performed (worst case O(m×n))

HashSet Approach (Alternative):

• Time:
  • flip(): O(1) to O(m×n) depending on how full the matrix is
  • reset(): O(k) where k is number of flips
• Space: O(k) for tracking flipped positions

Full Solution

The provided solution has significant issues as it doesn't implement random selection. The correct approach uses Fisher-Yates shuffle algorithm to ensure truly random, uniform selection of unflipped cells in O(1) time. The artifact above shows both the correct implementation and highlights why the original code fails to meet the problem requirements.

class Solution {
    int i=0,j=0;
     int m=0;int n=0;

    public Solution(int m, int n) {
        this.m=m;
        this.n=n;
    }

    public int[] flip() {
        j++;
        if(j==n){
            j=0;
            i++;
        }
        if(i==m){
            i=0;
            j=0;
        }


        return new int[]{i,j};

    }

    public void reset() {




    }
}

The Fisher-Yates approach is optimal because it:

1. Guarantees uniform random distribution
2. Ensures no duplicates without expensive checking
3. Maintains O(1) time complexity for flip operations
4. Uses space efficiently (only stores swapped positions)