algoadvance

Leetcode 519. Random Flip Matrix

Problem Statement

You are given the number of rows m and the number of columns n of a 2D binary matrix initialized with all 0s. Implement the FlipMatrix class:

You should decide to use neither a 2D array nor dynamic memory allocation tracked in real-time, not exceeding O(1) space complexity for the matrix representation.

Clarifying Questions

  1. Can we assume the matrix dimensions (m x n) are always greater than zero?
  2. Should the flip() function return the same position [row_id, col_id] if all elements have already been flipped to 1?

Based on typical problem constraints and observed behavior:

  1. Yes, we can assume matrix dimensions are greater than zero.
  2. Once all elements have been flipped to 1, a common approach is to throw an error or reset automatically, but this problem usually relies on continuing to flip even if the matrix was fully occupied.

Let’s proceed to the coding section.

Strategy

  1. We will simulate a 2D array using a single-dimensional list to keep mapping indices to positions.
  2. We choose and mark positions in a flattened list representation of the matrix.
  3. For efficiency, we use a hashmap to keep track of flipped positions to avoid O(n) space complexity.
  4. On calling flip(), randomly pick an index from available zero-positions and mark it flipped.
  5. On calling reset(), reset all data structures to start over.

Code

import java.util.*;

class FlipMatrix {
    private int m, n, total;
    private Map<Integer, Integer> map;
    private Random rand;

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

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

    public void reset() {
        this.total = m * n;
        this.map.clear();
    }
}

Time Complexity

  1. Initialization (FlipMatrix): O(1)
  2. Flipping (flip): O(1) - Constant time to generate and store mappings.
  3. Reset (reset): O(1) - Linear time in terms of clearing the map and resetting the counter.

This approach effectively minimizes space usage while maintaining constant-time complexity for the primary operations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI