2128. Remove All Ones With Row and Column Flips

You are given an m x n binary matrix grid.

In one operation, you can choose any row or column and flip each value in that row or colum (i.e., changing all 00's to 11's, and all 11's to 00's).

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

Example 1:

Example 1

Input: grid = [[0,1,0],[1,0,1],[0,1,0]]
Output: true
Explanation: One possible way to remove all 11's from grid is to:

  • Flip the middle row
  • Flip the middle column

Example 2:

Input: grid = [[1,1,0],[0,0,0],[0,0,0]]
Output: false
Explanation: It is impossible to remove all 11's from grid.

Input: grid = [[0]]
Output: true
Explanation: There are no 11's in grid.

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is either 00 or 11.

Solution

Brute Force

The first observation we can make is that for every row/column, we will either flip that row/column once or zero times. This is because if we flip a row/column twice, it will have no effect on the grid.

With this in mind, for each row and column, we can either choose to flip it or not flip it. If we brute force every combination, we will take O(MN)O(MN) to simulate each combination. Since there are O(2M+N)O(2^{M+N}) combinations, this gives us a time complexity of O(2M+N×MN)O(2^{M+N}\times MN). Let's look for a faster solution as this is way too slow.

Full Solution

Let's call grid reachable if it's possible to apply some row/column flips to remove all 00's.

We can observe that if each row/column is flipped at most once, there is only one set of rows and columns that can be flipped to set all cells to 00 (assuming a solution exists). Let's call these necessary rows and columns.

To check whether or not grid is reachable, we'll first flip all necessary columns, and then the necessary rows.

Let's first assume that we already flipped all necessary columns on grid. We can observe that grid is now reachable by only row flips if all rows have the same integer (i.e. all 00's or all 11's).

Example

Here, we have a grid reachable by only row flips as all rows have the same integer. We can remove all 11's from grid by flipping rows with all 11's. Here, we will flip rows 11 and 55.

Our goal is to figure out a way to flip some set of columns such that grid will only contain rows with all 00's or all 11's.

With that in mind, our algorithm will go as follows. First, find all cells in the first row of grid with a 11. For every cell (0,j) in the first row that's a 11, let's flip the jthj^{th} column so that the cell (0,j) becomes a 00. This is important as it causes the first row to have all 00's. At this point there are two cases to consider.

  • The first case is that the rest of the rows have all 00's or all 11's. In this case, we can conclude that grid is reachable and we'll return true.

  • The second case is that there exists a row that has a mix of 00's and 11's, which we don't want. In this case, we'll return false since we can observe that it's impossible to get all rows to have all 00's or all 11's. This is because if we try to change the other rows to have all 00's or 11's with more column flips, the content of the first row will change and it will no longer have all 00's.

Time Complexity

In the worst scenario, we will perform O(M)O(M) row flips and O(N)O(N) column flips. Since row flips take O(N)O(N) to simulate and column flips take O(M)O(M) to simulate, our total time complexity is O(NM)O(NM).

Time Complexity: O(NM)O(NM).

Space Complexity

Since we don't actually use additional arrays or lists, our space complexity is O(1)O(1).

Space Complexity: O(1)O(1).

C++ Solution

1class Solution {
2   public:
3    bool removeOnes(vector<vector<int>>& grid) {
4        int m = grid.size();  // get dimensions of grid
5        int n = grid[0].size();
6        for (int i = 0; i < n; i++) {  // flip columns so that first row only has 0's
7            if (grid[0][i] == 1) {
8                for (int j = 0; j < m; j++) {  // flips a column
9                    grid[j][i] = 1 - grid[j][i];
10                }
11            }
12        }
13        bool ans = true;
14        for (int i = 0; i < m; i++) {  // checks if each row has all 0's or all 1's
15            int sum = 0;
16            for (int j = 0; j < n; j++) {
17                sum += grid[i][j];
18            }
19            if (sum == 0 || sum == n) {
20                continue;
21            }
22            ans = false;
23        }
24        return ans;
25    }
26};

Java Solution

1class Solution {
2    public boolean removeOnes(int[][] grid) {
3        int m = grid.length; // get dimensions of grid
4        int n = grid[0].length;
5        for (int i = 0; i < n; i++) { // flip columns so that first row only has 0's
6            if (grid[0][i] == 1) {
7                for (int j = 0; j < m; j++) { // flips a column
8                    grid[j][i] = 1 - grid[j][i];
9                }
10            }
11        }
12        boolean ans = true;
13        for (int i = 0; i < m; i++) { // checks if each row has all 0's or all 1's
14            int sum = 0;
15            for (int j = 0; j < n; j++) {
16                sum += grid[i][j];
17            }
18            if (sum == 0 || sum == n) {
19                continue;
20            }
21            ans = false;
22        }
23        return ans;
24    }
25}

Python Solution

1class Solution:
2    def removeOnes(self, grid: List[List[int]]) -> bool:
3        m = len(grid)  # get dimensions of grid
4        n = len(grid[0])
5        for i in range(n):  # flip columns so that first row only has 0's
6            if grid[0][i] == 1:
7                for j in range(m):  # flips a column
8                    grid[j][i] = 1 - grid[j][i]
9        ans = True
10        for i in range(m):  # checks if each row has all 0's or all 1's
11            sum = 0
12            for j in range(n):
13                sum += grid[i][j]
14            if sum == 0 or sum == n:
15                continue
16            ans = False
17        return ans
18
💪
Level Up Your
Algo Skills

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫