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 bit flip changes 1 to 0 and 0 to 1. Return the minimum number of operations to make all the elements of the grid equal to 0.

Example 1

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

• Flip row 0: grid becomes [[1,0],[1,0]]
• Flip row 1: grid becomes [[1,0],[0,1]]
• Flip column 0: grid becomes [[0,0],[1,1]]
• Flip column 1: grid becomes [[0,0],[0,0]] There are a total of 4 operations.

Example 2

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

• Flip row 2: grid becomes [[0,0,0],[0,0,1],[0,0,0]]
• Flip column 2: grid becomes [[0,0,0],[0,0,0],[0,0,0]] There are a total of 2 operations.

Steps

1. Consider the first row: We can flip the bits of any row to make all elements of that row 0.
2. Process columns based on the first row: After making the first row all 0s (if needed), we'll examine the columns. If a column has a 1 in it, we flip that column. This ensures that the first row remains 0.
3. Check remaining rows: Finally, check the remaining rows. If a row contains a 1, it means that we must flip that row. This additional row flip may be needed even after column flips.

Explanation

The key insight is to focus on making the first row all zeros. If we can do this with minimum operations, the rest will follow logically. We'll use the first row as a reference. Any 1s in subsequent rows will require a row flip. We use column flips to ensure consistency with the first row.

Code

public class Solution {
    public int MinFlips(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;

        // Step 1: Minimize operations on the first row
        int rowFlips = 0;
        if (grid[0].Sum() > n / 2) {
            rowFlips++;
            for (int j = 0; j < n; j++) {
                grid[0][j] = 1 - grid[0][j];
            }
        }

        // Step 2: Process columns based on the first row
        int colFlips = 0;
        for (int j = 0; j < n; j++) {
            if (grid[0][j] == 1) {
                colFlips++;
                for (int i = 0; i < m; i++) {
                    grid[i][j] = 1 - grid[i][j];
                }
            }
        }

        // Step 3: Check remaining rows
        int remainingRowFlips = 0;
        for (int i = 1; i < m; i++) {
            if (grid[i].Sum() > 0) {
                remainingRowFlips++;
            }
        }

        return rowFlips + colFlips + remainingRowFlips;
    }
}

Complexity

• Time Complexity: O(m*n) - We iterate through the grid multiple times.
• Space Complexity: O(1) - We are only using a few variables to store the counts, not extra data structures proportional to the input size.