Remove All Ones With Row and Column Flips medium

Problem Statement

You are given a 0-indexed 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 0 to 1 and 1 to 0.

Return the minimum number of operations required to make all the bits in the matrix equal to 0.

Example 1:

Input: grid = [[0,1],[1,0]]
Output: 3
Explanation:
One possible way to make all bits equal to 0 is to:
- Flip the first row, making grid = [[1,0],[1,0]].
- Flip the second row, making grid = [[1,0],[0,1]].
- Flip the second column, making grid = [[1,1],[0,0]].
- Flip the first column, making grid = [[0,1],[1,0]].
- Flip the first row, making grid = [[1,0],[1,0]].
- Flip the second row, making grid = [[1,0],[0,1]].
- Flip the second column, making grid = [[0,0],[1,1]].
- Flip the first column, making grid = [[1,0],[0,1]].
- Flip the first row, making grid = [[0,0],[0,1]].
- Flip the second column, making grid = [[0,0],[0,0]].
The total number of operations is 3.
There is also a sequence of 3 operations to make all bits 0.

Example 2:

Input: grid = [[1,0],[0,1]]
Output: 2
Explanation:
One possible way is to flip the first row, then flip the second column, making the matrix all zeros.

Steps

1. Observe the first row: We can decide to flip the first row or not. This decision determines the state of the first row.

2. Determine column flips: Based on the state of the first row (flipped or not), we can determine whether or not we need to flip each column to make the entire first row 0. Count the number of column flips needed.

3. Check remaining rows: For each remaining row, check if it needs a row flip based on the column flip decisions. Count the number of row flips needed.

Explanation

The key insight is that we only need to consider the first row. Once we decide whether or not to flip the first row, the required flips for the columns are determined. Then, the number of row flips for the remaining rows can be calculated directly. The total number of operations will be the sum of column flips and the additional row flips. We can explore two possibilities: flipping the first row or not, and choose the solution with fewer operations.

Code

def min_flips(grid):
    """
    Calculates the minimum number of operations to make all bits 0.

    Args:
        grid: A list of lists representing the binary matrix.

    Returns:
        The minimum number of operations.
    """
    m, n = len(grid), len(grid[0])
    ans = float('inf')

    # Case 1: Don't flip the first row
    col_flips = 0
    for j in range(n):
        if grid[0][j] == 1:
            col_flips += 1
    row_flips = 0
    for i in range(1, m):
        row_sum = 0
        for j in range(n):
            if grid[i][j] != (grid[0][j]^0): # ^0 is XOR with 0 which has no effect. This simplifies the code.
                row_sum +=1
        if row_sum > n-row_sum:
            row_flips+=1
        
    ans = min(ans, col_flips + row_flips)


    # Case 2: Flip the first row
    col_flips = 0
    for j in range(n):
        if grid[0][j] == 0:
            col_flips += 1
    row_flips = 0
    for i in range(1, m):
        row_sum = 0
        for j in range(n):
            if grid[i][j] != (grid[0][j]^1):  #^1 is XOR with 1 (flips bit)
                row_sum +=1
        if row_sum > n-row_sum:
            row_flips+=1

    ans = min(ans, col_flips + row_flips +1) #add +1 because we flipped the first row

    return ans

Complexity

• Time Complexity: O(m*n), where 'm' and 'n' are the dimensions of the matrix. We iterate through the matrix a few times.
• Space Complexity: O(1). We use only a constant amount of extra space.