Description#
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 column (i.e., changing 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 or false
otherwise.
Example 1:
![](https://spcdn.pages.dev/leetcode/problems/2128.Remove%20All%20Ones%20With%20Row%20and%20Column%20Flips/images/image-20220103191300-1.png)
Input: grid = [[0,1,0],[1,0,1],[0,1,0]]
Output: true
Explanation: One possible way to remove all 1's from grid is to:
- Flip the middle row
- Flip the middle column
Example 2:
![](https://spcdn.pages.dev/leetcode/problems/2128.Remove%20All%20Ones%20With%20Row%20and%20Column%20Flips/images/image-20220103181204-7.png)
Input: grid = [[1,1,0],[0,0,0],[0,0,0]]
Output: false
Explanation: It is impossible to remove all 1's from grid.
Example 3:
![](https://spcdn.pages.dev/leetcode/problems/2128.Remove%20All%20Ones%20With%20Row%20and%20Column%20Flips/images/image-20220103181224-8.png)
Input: grid = [[0]]
Output: true
Explanation: There are no 1's in grid.
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j]
is either 0
or 1
.
Solutions#
Solution 1#
1
2
3
4
5
6
7
| class Solution:
def removeOnes(self, grid: List[List[int]]) -> bool:
s = set()
for row in grid:
t = tuple(row) if row[0] == grid[0][0] else tuple(x ^ 1 for x in row)
s.add(t)
return len(s) == 1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public boolean removeOnes(int[][] grid) {
Set<String> s = new HashSet<>();
int n = grid[0].length;
for (var row : grid) {
var cs = new char[n];
for (int i = 0; i < n; ++i) {
cs[i] = (char) (row[0] ^ row[i]);
}
s.add(String.valueOf(cs));
}
return s.size() == 1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
bool removeOnes(vector<vector<int>>& grid) {
unordered_set<string> s;
for (auto& row : grid) {
string t;
for (int x : row) {
t.push_back('0' + (row[0] == 0 ? x : x ^ 1));
}
s.insert(t);
}
return s.size() == 1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| func removeOnes(grid [][]int) bool {
s := map[string]bool{}
for _, row := range grid {
t := []byte{}
for _, x := range row {
if row[0] == 1 {
x ^= 1
}
t = append(t, byte(x)+'0')
}
s[string(t)] = true
}
return len(s) == 1
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| function removeOnes(grid: number[][]): boolean {
const s = new Set<string>();
for (const row of grid) {
if (row[0] === 1) {
for (let i = 0; i < row.length; i++) {
row[i] ^= 1;
}
}
const t = row.join('');
s.add(t);
}
return s.size === 1;
}
|