MEDIUM

Remove All Ones With Row and Column Flips

You are given a m x n binary matrix grid.

In one operation, you can choose any row or column and flip all values in that row or column (i.e., change all 0's to 1's and all 1's to 0's).

Return true if it is possible to remove all 1's from grid using any number of operations. Otherwise, return false.

Example

Input:

grid = [[0,1,0],[1,0,1],[0,1,0]]

Output:

true

Explanation: Flip the second row, then the second column.

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 300
grid[i][j] is 0 or 1

Solution: Greedy / Matrix Pattern

Time Complexity: O(mn)
Space Complexity: O(1)

C++

class Solution {
public:
    bool removeOnes(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        for (int i = 1; i < m; ++i) {
            bool flip = grid[i][0] != grid[0][0];
            for (int j = 0; j < n; ++j) {
                if ((grid[i][j] != grid[0][j]) != flip) return false;
            }
        }
        return true;
    }
};