Skip to main content

Minimum Number of Flips to Convert Binary Matrix to Zero Matrix

Description​

Given a binary matrix, the goal is to find the minimum number of flips required to convert the entire matrix to zeroes. You can flip any single cell or any row/column.

Problem Definition​

  • Input: A binary matrix matrix.
  • Output: Return the minimum number of flips required to convert the matrix to all zeroes.

Example​

  • Input:
    • matrix = [[0,0,1],[1,0,0],[0,1,0]]
  • Output:
    • 3 (flip the first row, second column, and third column).

Algorithm Overview​

  1. Iterate through the matrix and for each cell, determine if it contributes to the overall count of flips.
  2. Use dynamic programming to keep track of flips needed for each row and column.
  3. Return the total number of flips required.

Time Complexity​

  • O(m*n) - where m is the number of rows and n is the number of columns in the matrix.

C++ Implementation​

#include <iostream>
#include <vector>
using namespace std;

int minFlipsToZeroMatrix(vector<vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    int flips = 0;

    // Count the number of 1's in the matrix
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            flips += matrix[i][j];
        }
    }

    // The number of flips required is equal to the number of 1's
    return flips;
}

int main() {
    vector<vector<int>> matrix = {{0, 0, 1}, {1, 0, 0}, {0, 1, 0}};
    cout << "Minimum flips required: " << minFlipsToZeroMatrix(matrix) << endl;
    return 0;
}