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 true if it is possible to make all the elements of the grid to be zero using at most m + n operations. Otherwise, return false.

Example 1

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

• Flip row 1: [[0,1],[0,0]]
• Flip column 0: [[1,1],[0,0]]
• Flip column 1: [[1,0],[0,1]]
• Flip row 0: [[0,1],[0,1]]
• Flip column 1: [[0,0],[0,0]] It takes 5 operations, which is less than m + n = 4. It's possible to make all elements of the grid to be zero.

Example 2

Input: grid = [[0,1,0],[1,0,1],[0,0,0]] Output: false Explanation: It is not possible to make all the elements to be zero.

Steps

The key idea is to observe that flipping rows and columns is commutative. We can choose to prioritize flipping rows first, then columns, or vice versa. We will use the following strategy:

1. Process Rows: Iterate through each row. If the first element of the row is 1, flip the entire row. This ensures that the first column will be all 0s after this step.
2. Process Columns: Iterate through each column (excluding the first column, which is already handled). If an element in the first row of that column is 1, flip the entire column. This ensures that the remaining elements will be all 0s.

If after this process, all elements are 0s, then it is possible, and we return true. Otherwise, it is not possible, and we return false.

Explanation

The algorithm leverages the fact that flipping a row or a column multiple times is equivalent to not flipping it at all (an even number of flips). Therefore, if we can achieve a state where all elements are 0, it will always be within the m + n operations bound. By focusing on the first row and first column, we simplify the process and easily determine the feasibility.

Code

function removeOnes(grid: number[][]): boolean {
    const m = grid.length;
    const n = grid[0].length;

    // Process rows
    for (let i = 0; i < m; i++) {
        if (grid[i][0] === 1) {
            for (let j = 0; j < n; j++) {
                grid[i][j] = 1 - grid[i][j];
            }
        }
    }

    // Process columns
    for (let j = 1; j < n; j++) {
        if (grid[0][j] === 1) {
            for (let i = 0; i < m; i++) {
                grid[i][j] = 1 - grid[i][j];
            }
        }
    }

    // Check if all elements are 0
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                return false;
            }
        }
    }

    return true;
};

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 extra space is used proportional to the input size.