Remove All Ones With Row and Column Flips medium

Problem Statement

You are given an m x n binary matrix grid. In one operation, you can choose any row or column and flip all the bits in that row or column. A flip consists of changing 1 to 0 and 0 to 1. Return the minimum number of operations needed to make all the elements of the grid equal to 0. If it's impossible to make all elements equal to 0, return -1.

Example 1

Input: grid = [[0,1],[1,0]] Output: 3 Explanation:

• Flip row 0: [[1,0],[1,0]]
• Flip row 1: [[1,0],[0,1]]
• Flip column 1: [[1,1],[0,0]]

Then, flip column 0 to get the result: [[0,0],[0,0]]. The total number of operations is 4.

However, another sequence of operations can lead to fewer operations. We can achieve it in 3 operations:

• Flip column 0: [[1,1],[0,0]]
• Flip column 1: [[1,0],[0,1]]
• Flip row 1: [[1,0],[1,0]] Then flip row 0 to get [[0,0],[0,0]]. The total number of operations is 4.

The optimal solution achieves it in 3 operations:

• Flip row 0: [[1,0],[1,0]]
• Flip column 1: [[1,1],[0,0]]
• Flip row 1: [[1,1],[1,1]] Then flip any row to get [[0,0],[0,0]]. The total number of operations is 3.

Example 2

Input: grid = [[1,0],[0,1]] Output: 2

Steps

1. Consider the first row: We can choose to flip or not flip the first row. This decision will affect the number of operations needed for subsequent rows and columns.

2. Iterate through rows: For each row, decide whether to flip it or not based on minimizing operations. We can track the number of 1s in each column. Flipping a row changes the count of 1s in each column.

3. Iterate through columns: Similarly, iterate through the columns. After potentially flipping rows, we determine the minimum number of column flips to achieve all zeros.

4. Calculate total operations: Add the number of row flips and column flips.

5. Check for impossibility: If we can't make all elements 0, return -1. (This scenario won't happen with binary matrices, but the problem statement allows for the possibility.)

Explanation

The key insight is that the order of row and column flips does not affect the final result. We can make our decision about flipping rows independently from flipping columns. We only need to count how many rows and columns need to be flipped to reach a state where all elements are 0.

The optimization comes from choosing whether or not to flip each row strategically. Let's say we are looking at row i. The number of 1s in this row determines whether flipping it will lead to fewer or more column flips. If the number of 1s in that row is greater than the number of 0s, flipping it reduces the number of column flips we'll need later.

Code

#include <vector>
#include <algorithm>

using namespace std;

int minFlips(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    int rowFlips = 0;
    int colFlips = 0;

    // Iterate through rows and decide whether to flip
    for (int i = 0; i < m; ++i) {
        int ones = 0;
        for (int j = 0; j < n; ++j) {
            ones += grid[i][j];
        }
        if (ones > n / 2) { // Flip if more 1s than 0s
            rowFlips++;
            for (int j = 0; j < n; ++j) {
                grid[i][j] = 1 - grid[i][j];
            }
        }
    }

    // Iterate through columns and decide whether to flip
    for (int j = 0; j < n; ++j) {
        int ones = 0;
        for (int i = 0; i < m; ++i) {
            ones += grid[i][j];
        }
        if (ones > 0) { // Flip if any 1s left
            colFlips++;
            for (int i = 0; i < m; ++i) {
                grid[i][j] = 1 - grid[i][j];
            }
        }
    }

    return rowFlips + colFlips;
}

Complexity

• Time Complexity: O(m * n), where 'm' and 'n' are the dimensions of the grid. We iterate through the grid twice.
• Space Complexity: O(1). We modify the grid in place; no additional data structures are used that scale with the input size.