1252. Cells with Odd Values in a Matrix LeetCode Solution
In this guide, you will get 1252. Cells with Odd Values in a Matrix LeetCode Solution with the best time and space complexity. The solution to Cells with Odd Values in a Matrix problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Cells with Odd Values in a Matrix
There is an m x n matrix that is initialized to all 0’s. There is also a 2D array indices where each indices[i] = [ri, ci] represents a 0-indexed location to perform some increment operations on the matrix.
For each location indices[i], do both of the following:
Increment all the cells on row ri.
Increment all the cells on column ci.
Given m, n, and indices, return the number of odd-valued cells in the matrix after applying the increment to all locations in indices.
Example 1:
Input: m = 2, n = 3, indices = [[0,1],[1,1]]
Output: 6
Explanation: Initial matrix = [[0,0,0],[0,0,0]].
After applying first increment it becomes [[1,2,1],[0,1,0]].
The final matrix is [[1,3,1],[1,3,1]], which contains 6 odd numbers.
Example 2:
Input: m = 2, n = 2, indices = [[1,1],[0,0]]
Output: 0
Explanation: Final matrix = [[2,2],[2,2]]. There are no odd numbers in the final matrix.
Constraints:
1 <= m, n <= 50
1 <= indices.length <= 100
0 <= ri < m
0 <= ci < n
Follow up: Could you solve this in O(n + m + indices.length) time with only O(n + m) extra space?
Complexity Analysis
Time Complexity: O(mn + |\texttt{indices}|)
Space Complexity: O(m + n)
1252. Cells with Odd Values in a Matrix LeetCode Solution in C++
class Solution {
public:
int oddCells(int m, int n, vector<vector<int>>& indices) {
int ans = 0;
// rows[i] and cols[i] :=
// true (flipped even times) / false (flipped odd times)
vector<bool> rows(m);
vector<bool> cols(n);
for (const vector<int>& index : indices) {
rows[index[0]] = rows[index[0]] ^ true;
cols[index[1]] = cols[index[1]] ^ true;
}
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
ans += rows[i] ^ cols[j];
return ans;
}
}; /* code provided by PROGIEZ */
1252. Cells with Odd Values in a Matrix LeetCode Solution in Java
class Solution {
public int oddCells(int m, int n, int[][] indices) {
int ans = 0;
// rows[i] and cols[i] :=
// true (flipped even times) / false (flipped odd times)
boolean[] rows = new boolean[n];
boolean[] cols = new boolean[n];
for (int[] index : indices) {
rows[index[0]] = rows[index[0]] ^ true;
cols[index[1]] = cols[index[1]] ^ true;
}
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (rows[i] ^ cols[j])
++ans;
return ans;
}
} // code provided by PROGIEZ
1252. Cells with Odd Values in a Matrix LeetCode Solution in Python
class Solution:
def oddCells(self, m: int, n: int, indices: list[list[int]]) -> int:
# rows[i] and cols[i] :=
# true (flipped even times) / false (flipped odd times)
rows = [False] * m
cols = [False] * n
for r, c in indices:
rows[r] ^= True
cols[c] ^= True
return sum(rows[i] ^ cols[j]
for i in range(m)
for j in range(n)) # code by PROGIEZ
