LeetCode 2128. Remove All Ones With Row and Column Flips Solution
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 's to 's, and all 's to 's).
Return true
if it is possible to remove all 1
's from grid
using any number of operations or false
otherwise.
Example 1:
Input: grid = [[0,1,0],[1,0,1],[0,1,0]]
Output: true
Explanation: One possible way to remove all '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 's from grid
.

Input: grid = [[0]]
Output: true
Explanation: There are no 's in grid
.
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j]
is either or .
Problem Link: https://leetcode.com/problems/remove-all-ones-with-row-and-column-flips/
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 to simulate each combination. Since there are combinations, this gives us a time complexity of . 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 '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 (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 's or all 's).
Example

Here, we have a grid
reachable by only row flips as all rows have the same integer. We can remove all 's from grid
by flipping rows with all 's. Here, we will flip rows and .
Our goal is to figure out a way to flip some set of columns such that grid
will only contain rows with all 's or all 's.
With that in mind, our algorithm will go as follows. First, find all cells in the first row of grid
with a . For every cell (0,j)
in the first row that's a , let's flip the column so that the cell (0,j)
becomes a . This is important as it causes the first row to have all 's. At this point there are two cases to consider.
-
The first case is that the rest of the rows have all 's or all 's. In this case, we can conclude that
grid
is reachable and we'll returntrue
. -
The second case is that there exists a row that has a mix of 's and '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 's or all 's. This is because if we try to change the other rows to have all 's or 's with more column flips, the content of the first row will change and it will no longer have all 's.
Time Complexity
In the worst scenario, we will perform row flips and column flips. Since row flips take to simulate and column flips take to simulate, our total time complexity is .
Time Complexity: .
Space Complexity
Since we don't actually use additional arrays or lists, our space complexity is .
Space Complexity: .
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