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 '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 .
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
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorWhich of these pictures shows the visit order of a depth-first search?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.