1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

HardBit ManipulationBreadth-First SearchArrayMatrix
Leetcode Link

Problem Description

In this problem, we're presented with a binary matrix mat with dimensions m x n, where each element is either a 0 or a 1. The task is to transform this binary matrix into a zero matrix, where all elements are 0. The rules for transformation are unique – in a single step, you can pick any cell in the matrix and flip its value, as well as the values of its four direct neighbors (above, below, left, and right). If there is no neighbor (because the cell is on the edge or corner of the matrix), only the cells available are flipped. The goal is to perform this step as few times as possible to get a zero matrix. If it's impossible to convert the matrix to a zero matrix, the function should return -1.

Intuition

Given the constraints of the problem, a brute force approach where we try to flip each cell until we get a zero matrix might not be efficient, especially when the number of possible states of the matrix grows exponentially with the size of the matrix. A better approach is to model each state of the matrix as a node in a graph and perform a breadth-first search (BFS) to find the shortest path to the zero matrix state.

We can represent the state of the matrix as an integer by thinking about the matrix as a binary number where each 1 or 0 contributes to a bit in this number. We initialize the state by converting the matrix mat into an integer, where the bit position is determined by the cell’s row and column indexes.

The BFS algorithm starts with the initial state of the matrix. For each state visited, we generate all possible states that can be reached by flipping each cell once and pushing these states onto a queue if they have not been visited before. When generating these new states, we make sure to include the flip of the neighbors if they exist.

If, at any point, we reach a state where all bits are 0, which means our matrix is a zero matrix, we return the number of steps taken to reach that state. If the queue gets exhausted without reaching a zero matrix, we conclude that it's impossible to achieve a zero matrix and return -1.

The deque is used for efficient popping of elements from the front of the queue, and a set vis keeps track of visited states to avoid redundant searches and loops. The dirs array is used to simplify the calculation of neighbor indices during the flipping process.

Solution Approach

The solution utilizes a breadth-first search (BFS) algorithm to explore the states space created by flipping cells in the matrix. The BFS approach is suitable as it finds the shortest path (minimum number of flips) to reach the goal state (a zero matrix). Let's walk through the implementation steps:

  1. State representation and initial state: First, we need to represent the matrix state as a single integer. This is achieved by converting the 2D binary matrix into a binary number and then to an integer. Each bit in this integer corresponds to a cell in the matrix, where the bit's index is determined by the cell’s row and column (i * n + j), and is set to 1 if the cell's value is 1.

    1state = sum(1 << (i * n + j) for i in range(m) for j in range(n) if mat[i][j])
  2. Data Structures: We use a deque for storing and retrieving states to be processed in FIFO order, which is integral for BFS, and a set named vis to record the states we've already visited. This helps in avoiding processing the same state multiple times.

    1q = deque([state])
    2vis = {state}
  3. Traversal and generation of next states: We loop while there are states in the queue. For each state, we attempt to find the next states by flipping each cell and its neighbors.

    1for i in range(m):
    2    for j in range(n):
    3        # Code to calculate the flipped state
    4        ...
    5        if nxt not in vis:
    6            vis.add(nxt)
    7            q.append(nxt)
  4. Neighboring cells handling: To calculate the flipped state, we create an array dirs that simplifies navigating through a cell's neighbors. With each flip, the corresponding bit for the cell and its neighbors is toggled in the integer representation of the matrix.

    1dirs = [0, -1, 0, 1, 0, 0]
    2for k in range(5):
    3    x, y = i + dirs[k], j + dirs[k + 1]
    4    ...
  5. Goal state check: During BFS, after generating a new state, we check if it equals 0, which means the matrix is now a zero matrix. If that's the case, we return the number of steps taken to reach this state.

    1if state == 0:
    2    return ans
  6. Increment steps and return answer: We keep track of the number of steps taken with a variable ans. If we exhaust all possible states and cannot reach the zero state, we return -1.

    1ans += 1
    2...
    3return -1

This solution explores all possible configurations of the matrix. With every level of BFS representing one more flip of any cell, we find the minimum number of steps to reach the zero matrix. The use of BFS ensures that once we reach a zero matrix, it is guaranteed to be in the minimum possible number of steps.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's use a small example matrix to illustrate the solution approach. Consider a 2 x 2 binary matrix:

1mat = [[1, 0],
2       [0, 1]]

To convert this matrix to a zero matrix using the solution approach, follow these steps:

  1. State representation and initial state: The initial state of this matrix can be represented as an integer where each bit corresponds to one element in the matrix. In this case, the top-left 1 represents the most significant bit, and the bottom-right 1 is the least significant bit, resulting in an integer 1010 in binary or 10 in decimal.

  2. Data Structures: Initialize the queue with the starting state (10) and create a visited set with the same initial state.

1q = deque([10])
2vis = {10}
  1. Traversal and generation of next states: Begin the BFS loop. Since the matrix has four cells, there are four possible flips we can make for this state (one for each cell).

  2. Neighboring cells handling: For the top-left cell (0, 0), flipping it would also flip its neighbor to the right and beneath it. The resulting state would be:

    1Flipped matrix: [[0, 1],
    2                 [1, 1]]
    3State: 0111 (binary) or 7 (decimal)

    For the bottom-right cell (1, 1), flipping it would also flip its neighbor to the left and above it:

    1Flipped matrix: [[1, 1],
    2                 [1, 0]]
    3State: 1101 (binary) or 13 (decimal)

    Continue this process for the other cells (0, 1) and (1, 0). You would end up with states 14 and 11, respectively.

  3. Goal state check and increment steps: None of the new states are zero, so increment the step counter and put the new states on the queue if they have not been visited.

  4. Repeat steps 3-5: Continue with the BFS. Find that flipping the top-right cell (0, 1) in the matrix where the state is 11 gives the zero matrix:

    1Original state: 1011 (11 in decimal)
    2Flipped matrix: [[1, 0],
    3                 [0, 0]]
    4New state: 1000 (8 in decimal)
    5
    6Flipping bottom-left cell after that gives zero matrix:
    7Original state: 1000 (8 in decimal)
    8Flipped matrix: [[0, 0],
    9                 [0, 0]]
    10New state: 0000 (0 in decimal)

    Since the new state represents a zero matrix (0000 in binary or 0 in decimal), the BFS has reached the goal.

  5. Return the answer: The number of steps taken to reach the goal state is the answer. In this example, it took two steps to reach a zero matrix.

Thus, the matrix [[1, 0], [0, 1]] can be converted to a zero matrix in a minimum of two steps.

Python Solution

1from collections import deque
2from typing import List
3
4class Solution:
5    def minFlips(self, mat: List[List[int]]) -> int:
6        rows, cols = len(mat), len(mat[0])
7      
8        # The initial state of the mat converted into a bitmask.
9        initial_state = sum(1 << (i * cols + j) for i in range(rows) for j in range(cols) if mat[i][j])
10      
11        # Queue for BFS
12        queue = deque([initial_state])
13      
14        # Keeping track of visited states to avoid repetition
15        visited = {initial_state}
16      
17        # Number of flips needed
18        flips = 0
19      
20        # These are the directions for the adjacent cells including the cell itself (5 moves)
21        directions = [0, -1, 0, 1, 0, 0]
22      
23        # BFS to find the minimum number of flips
24        while queue:
25            # Process nodes level by level
26            for _ in range(len(queue)):
27                current_state = queue.popleft()
28              
29                # If the current state represents all zeros, we have found our answer
30                if current_state == 0:
31                    return flips
32              
33                # Try flipping each cell in the matrix
34                for i in range(rows):
35                    for j in range(cols):
36                        next_state = current_state
37                      
38                        # Flip the switch for cell and its neighbors
39                        for k in range(5):
40                            x, y = i + directions[k], j + directions[k + 1]
41                          
42                            # Check if the new (x, y) position is outside the matrix bounds
43                            if 0 <= x < rows and 0 <= y < cols:
44                                # Flip the bit at position (x, y)
45                                next_state ^= 1 << (x * cols + y)
46                      
47                        # Check if we have already encountered this state
48                        if next_state not in visited:
49                            visited.add(next_state)
50                            queue.append(next_state)
51          
52            # Increment the number of flips after each level
53            flips += 1
54      
55        # If no solution has been found return -1
56        return -1
57

Java Solution

1class Solution {
2    public int minFlips(int[][] mat) {
3        int rows = mat.length, cols = mat[0].length;
4        // Convert the 2D matrix to a 1D state representation
5        int initialState = 0;
6        for (int i = 0; i < rows; i++) {
7            for (int j = 0; j < cols; j++) {
8                if (mat[i][j] == 1) {
9                    initialState |= 1 << (i * cols + j);
10                }
11            }
12        }
13      
14        // Queue for BFS (Breadth-First Search)
15        Deque<Integer> queue = new ArrayDeque<>();
16        queue.offer(initialState);
17      
18        // Set to keep track of visited states
19        Set<Integer> visited = new HashSet<>();
20        visited.add(initialState);
21      
22        // Distance variable counting the number of flips
23        int numFlips = 0;
24      
25        // Direction vectors representing the adjacent cells to the current cell
26        int[] dirs = {0, 1, 0, -1, 0}; // right, down, left, up
27      
28        // Begin BFS
29        while (!queue.isEmpty()) {
30            int size = queue.size();
31            while (size-- > 0) {
32                int currentState = queue.poll();
33                // If we reach the state with all 0s, return the number of flips
34                if (currentState == 0) {
35                    return numFlips;
36                }
37                // Iterate through all cells of the matrix
38                for (int i = 0; i < rows; i++) {
39                    for (int j = 0; j < cols; j++) {
40                        int nextState = currentState;
41                        // Flip the current cell and adjacent cells
42                        for (int k = 0; k < 5; k++) { // 5 because we are including the cell itself
43                            int x = i + dirs[k];
44                            int y = j + dirs[k - 1];
45                            // Check if the new coordinate is legal
46                            if (x >= 0 && x < rows && y >= 0 && y < cols) {
47                                nextState ^= 1 << (x * cols + y);
48                            }
49                        }
50                        // If we haven't already visited this state, add it to the queue
51                        if (!visited.contains(nextState)) {
52                            visited.add(nextState);
53                            queue.offer(nextState);
54                        }
55                    }
56                }
57            }
58            // Increment the flips counter after each level in BFS
59            numFlips++;
60        }
61        // If there's no way to turn off all the bulbs, return -1
62        return -1;
63    }
64}
65

C++ Solution

1class Solution {
2public:
3    int minFlips(vector<vector<int>>& mat) {
4        int rows = mat.size();           // Number of rows in the matrix
5        int cols = mat[0].size();        // Number of columns in the matrix
6        int initialState = 0;            // Variable to store the initial state of the matrix
7      
8        // Convert the 2D matrix state to a bit representation stored in a single integer
9        for (int i = 0; i < rows; ++i) {
10            for (int j = 0; j < cols; ++j) {
11                if (mat[i][j]) {
12                    initialState |= (1 << (i * cols + j));
13                }
14            }
15        }
16      
17        // Queue to store all the states to be checked
18        queue<int> statesQueue{{initialState}};
19        // Set to keep track of visited states
20        unordered_set<int> visited{{initialState}};
21        // Counter for the number of flips
22        int minFlipsCount = 0;
23        // Direction vectors represent the 4 directions and the cell itself
24        vector<int> directionDeltas = {0, 1, 0, -1, 0};
25
26        // BFS to find the minimum number of flips
27        while (!statesQueue.empty()) {
28            int queueSize = statesQueue.size();
29            for (int t = 0; t < queueSize; ++t) {
30                int currentState = statesQueue.front();
31                if (currentState == 0) return minFlipsCount; // If state is zero, matrix is all 0 and we are done
32                statesQueue.pop();
33
34                // Iterate through every cell in the matrix
35                for (int i = 0; i < rows; ++i) {
36                    for (int j = 0; j < cols; ++j) {
37                        int nextState = currentState; // Copy of the current state
38                      
39                        // Toggle the bit of the current cell and adjacent cells
40                        for (int k = 0; k < 5; ++k) {
41                            int x = i + directionDeltas[k];      // Row index after applying delta
42                            int y = j + directionDeltas[k + 1]; // Col index after applying delta
43
44                            // Check for valid cell (inside boundary)
45                            if (x >= 0 && x < rows && y >= 0 && y < cols) {
46                                nextState ^= 1 << (x * cols + y); // XOR to flip the bit
47                            }
48                        }
49
50                        // Only process this next state if it hasn't been visited yet
51                        if (!visited.count(nextState)) {
52                            visited.insert(nextState);     // Mark next state as visited
53                            statesQueue.push(nextState);   // Add next state to queue for processing
54                        }
55                    }
56                }
57            }
58            minFlipsCount++; // Increment the flip count after processing all states of the current level
59        }
60
61        // If we can't turn all cells to 0, return -1
62        return -1;
63    }
64};
65

Typescript Solution

1// Define the interface for a 2D array of numbers
2interface Matrix extends Array<Array<number>> {}
3
4// Global variables
5let rows: number;
6let cols: number;
7
8// Function to convert the 2D matrix state to a bit representation stored in a single integer
9function matToBit(mat: Matrix): number {
10    let state = 0;
11    for (let i = 0; i < rows; ++i) {
12        for (let j = 0; j < cols; ++j) {
13            if (mat[i][j]) {
14                state |= (1 << (i * cols + j));
15            }
16        }
17    }
18    return state;
19}
20
21// Function to flip the bits of the current cell and adjacent cells
22function flipBits(state: number, cellRow: number, cellCol: number): number {
23    const directionDeltas = [0, 1, 0, -1, 0];
24    for (let k = 0; k < 5; ++k) {
25        const x = cellRow + directionDeltas[k]; // Row index after applying delta
26        const y = cellCol + directionDeltas[k + 1]; // Col index after applying delta
27      
28        // Check for valid cell (inside boundary)
29        if (x >= 0 && x < rows && y >= 0 && y < cols) {
30            state ^= 1 << (x * cols + y); // XOR to flip the bit
31        }
32    }
33    return state;
34}
35
36// BFS function to find the minimum number of flips
37function minFlips(mat: Matrix): number {
38    rows = mat.length; // Number of rows in the matrix
39    cols = mat[0].length; // Number of columns in the matrix
40    const initialState = matToBit(mat); // Initial state of the matrix
41
42    // Queue to store all the states to be checked
43    const statesQueue: number[] = [initialState];
44    // Set to keep track of visited states
45    const visited = new Set<number>([initialState]);
46    // Counter for the number of flips
47    let minFlipsCount = 0;
48
49    // BFS to find the minimum number of flips
50    while (statesQueue.length > 0) {
51        const queueSize = statesQueue.length;
52        for (let t = 0; t < queueSize; ++t) {
53            const currentState = statesQueue.shift();
54            if (currentState === 0) return minFlipsCount; // If state is zero, matrix is all 0 and we are done
55
56            // Iterate through every cell in the matrix
57            for (let i = 0; i < rows; ++i) {
58                for (let j = 0; j < cols; ++j) {
59                    const nextState = flipBits(currentState, i, j);
60
61                    // Only process this next state if it hasn't been visited yet
62                    if (!visited.has(nextState)) {
63                        visited.add(nextState); // Mark next state as visited
64                        statesQueue.push(nextState); // Add next state to queue for processing
65                    }
66                }
67            }
68        }
69        minFlipsCount++; // Increment the flip count after processing all states of the current level
70    }
71
72    // If we can't turn all cells to 0, return -1
73    return -1;
74}
75

Time and Space Complexity

The provided Python code aims to find the minimum number of flips to convert a given binary matrix into a matrix with all zeros by flipping a cell and all its adjacent cells (up, down, left, and right) at once. The solution uses a breadth-first search (BFS) algorithm to explore all possible flip combinations, represented as states of the matrix.

Time Complexity:

  • The time complexity of the algorithm is influenced by several factors: the size of the matrix, the number of possible states, and the BFS traversal.
  • The initial state is computed using a double loop through the m * n matrix, which adds a O(m * n) factor.
  • The BFS queue can hold at most 2^(m * n) states, because each cell can either be flipped or not, which gives two possibilities per cell.
  • The BFS loop iterates until either all states have been visited or the target state (all zeros) has been found.
  • Inside the BFS, for each state, we iterate over all m * n cells and for each cell, in the worst case, flip itself and its four adjacent cells. This gives us a factor of O(m * n * 5) for generating new states per state.
  • Therefore, each state has potentially m * n next states. Concerning the number of states, the factor would be O(m * n * 2^(m * n)).
  • Combining these factors, the worst-case time complexity is O((m * n) * (m * n * 2^(m * n))) = O((m^2 * n^2) * 2^(m * n)).

Space Complexity:

  • The space complexity is primarily determined by the storage of visited states and the BFS queue.
  • The set of visited states can grow to hold a maximum of 2^(m * n) unique states.
  • The BFS queue also has the capacity to store at most 2^(m * n) states at one time.
  • Therefore, the space complexity of the algorithm is O(2^(m * n)), which accounts for the storage of all possible states of the matrix.

In summary, while the BFS approach is sound for small matrices, both time and space complexity grow extremely quickly as the size of the matrix increases, due to the combinatorial nature of the problem.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫