1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix LeetCode Solution
In this guide, you will get 1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Flips to Convert Binary Matrix to Zero Matrix problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Number of Flips to Convert Binary Matrix to Zero Matrix
Given a m x n binary matrix mat. In one step, you can choose one cell and flip it and all the four neighbors of it if they exist (Flip is changing 1 to 0 and 0 to 1). A pair of cells are called neighbors if they share one edge.
Return the minimum number of steps required to convert mat to a zero matrix or -1 if you cannot.
A binary matrix is a matrix with all cells equal to 0 or 1 only.
A zero matrix is a matrix with all cells equal to 0.
Example 1:
Input: mat = [[0,0],[0,1]]
Output: 3
Explanation: One possible solution is to flip (1, 0) then (0, 1) and finally (1, 1) as shown.
Input: mat = [[0]]
Output: 0
Explanation: Given matrix is a zero matrix. We do not need to change it.
Example 3:
Input: mat = [[1,0,0],[1,0,0]]
Output: -1
Explanation: Given matrix cannot be a zero matrix.
Constraints:
m == mat.length
n == mat[i].length
1 <= m, n <= 3
mat[i][j] is either 0 or 1.
Complexity Analysis
Time Complexity: O(mn \cdot 2^{mn})
Space Complexity: O(2^{mn})
1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix LeetCode Solution in C++
class Solution {
public:
int minFlips(vector<vector<int>>& mat) {
const int m = mat.size();
const int n = mat[0].size();
const int hash = getHash(mat, m, n);
if (hash == 0)
return 0;
constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
queue<int> q{{hash}};
unordered_set<int> seen{hash};
for (int step = 1; !q.empty(); ++step) {
for (int sz = q.size(); sz > 0; --sz) {
const int curr = q.front();
q.pop();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int next = curr ^ 1 << (i * n + j);
// Flie the four neighbors.
for (const auto& [dx, dy] : dirs) {
const int x = i + dx;
const int y = j + dy;
if (x < 0 || x == m || y < 0 || y == n)
continue;
next ^= 1 << (x * n + y);
}
if (next == 0)
return step;
if (seen.contains(next))
continue;
q.push(next);
seen.insert(next);
}
}
}
}
return -1;
}
private:
int getHash(const vector<vector<int>>& mat, int m, int n) {
int hash = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (mat[i][j])
hash |= 1 << (i * n + j);
return hash;
}
}; /* code provided by PROGIEZ */
1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix LeetCode Solution in Java
class Solution {
public int minFlips(int[][] mat) {
final int m = mat.length;
final int n = mat[0].length;
final int hash = getHash(mat, m, n);
if (hash == 0)
return 0;
final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
Queue<Integer> q = new ArrayDeque<>(List.of(hash));
Set<Integer> seen = new HashSet<>(Arrays.asList(hash));
for (int step = 1; !q.isEmpty(); ++step) {
for (int sz = q.size(); sz > 0; --sz) {
final int curr = q.poll();
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
int next = curr ^ 1 << (i * n + j);
// Flie the four neighbors.
for (int[] dir : dirs) {
final int x = i + dir[0];
final int y = j + dir[1];
if (x < 0 || x == m || y < 0 || y == n)
continue;
next ^= 1 << (x * n + y);
}
if (next == 0)
return step;
if (seen.contains(next))
continue;
q.offer(next);
seen.add(next);
}
}
}
}
return -1;
}
private int getHash(int[][] mat, int m, int n) {
int hash = 0;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (mat[i][j] == 1)
hash |= 1 << (i * n + j);
return hash;
}
} // code provided by PROGIEZ
1284. Minimum Number of Flips to Convert Binary Matrix to Zero Matrix LeetCode Solution in Python
class Solution:
def minFlips(self, mat: list[list[int]]) -> int:
m = len(mat)
n = len(mat[0])
hash = self._getHash(mat, m, n)
if hash == 0:
return 0
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
step = 0
q = collections.deque([hash])
seen = {hash}
while q:
step += 1
for _ in range(len(q)):
curr = q.popleft()
for i in range(m):
for j in range(n):
next = curr ^ 1 << (i * n + j)
# Flie the four neighbors.
for dx, dy in dirs:
x = i + dx
y = j + dy
if x < 0 or x == m or y < 0 or y == n:
continue
next ^= 1 << (x * n + y)
if next == 0:
return step
if next in seen:
continue
q.append(next)
seen.add(next)
return -1
def _getHash(self, mat: list[list[int]], m: int, n: int) -> int:
hash = 0
for i in range(m):
for j in range(n):
if mat[i][j]:
hash |= 1 << (i * n + j)
return hash # code by PROGIEZ
