LeetCode - Difference Between Ones and Zeros in Row and Column
Problem statement
You are given a 0-indexed m x n binary matrix grid.
A 0-indexed m x n difference matrix diff is created with the following procedure:
Let the number of ones in the
ithrow beonesRowi.Let the number of ones in the
jthcolumn beonesColj.Let the number of zeros in the
ithrow bezerosRowi.Let the number of zeros in the
jthcolumn bezerosColj.diff[i][j] = onesRowi + onesColj - zerosRowi - zerosColj
Return the difference matrix diff.
Problem statement taken from: https://leetcode.com/problems/difference-between-ones-and-zeros-in-row-and-column
Example 1:
Input: grid = [[0, 1, 1], [1, 0, 1], [0, 0, 1]]
Output: [[0, 0, 4], [0, 0, 4], [-2, -2, 2]]
Explanation:
- diff[0][0] = onesRow0 + onesCol0 - zerosRow0 - zerosCol0 = 2 + 1 - 1 - 2 = 0
- diff[0][1] = onesRow0 + onesCol1 - zerosRow0 - zerosCol1 = 2 + 1 - 1 - 2 = 0
- diff[0][2] = onesRow0 + onesCol2 - zerosRow0 - zerosCol2 = 2 + 3 - 1 - 0 = 4
- diff[1][0] = onesRow1 + onesCol0 - zerosRow1 - zerosCol0 = 2 + 1 - 1 - 2 = 0
- diff[1][1] = onesRow1 + onesCol1 - zerosRow1 - zerosCol1 = 2 + 1 - 1 - 2 = 0
- diff[1][2] = onesRow1 + onesCol2 - zerosRow1 - zerosCol2 = 2 + 3 - 1 - 0 = 4
- diff[2][0] = onesRow2 + onesCol0 - zerosRow2 - zerosCol0 = 1 + 1 - 2 - 2 = -2
- diff[2][1] = onesRow2 + onesCol1 - zerosRow2 - zerosCol1 = 1 + 1 - 2 - 2 = -2
- diff[2][2] = onesRow2 + onesCol2 - zerosRow2 - zerosCol2 = 1 + 3 - 2 - 0 = 2
Example 2:
Input: grid = [[1, 1, 1], [1, 1, 1]]
Output: [[5, 5, 5], [5, 5, 5]]
Explanation:
- diff[0][0] = onesRow0 + onesCol0 - zerosRow0 - zerosCol0 = 3 + 2 - 0 - 0 = 5
- diff[0][1] = onesRow0 + onesCol1 - zerosRow0 - zerosCol1 = 3 + 2 - 0 - 0 = 5
- diff[0][2] = onesRow0 + onesCol2 - zerosRow0 - zerosCol2 = 3 + 2 - 0 - 0 = 5
- diff[1][0] = onesRow1 + onesCol0 - zerosRow1 - zerosCol0 = 3 + 2 - 0 - 0 = 5
- diff[1][1] = onesRow1 + onesCol1 - zerosRow1 - zerosCol1 = 3 + 2 - 0 - 0 = 5
- diff[1][2] = onesRow1 + onesCol2 - zerosRow1 - zerosCol2 = 3 + 2 - 0 - 0 = 5
Constraints:
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 10^5
- 1 <= m * n <= 10^5
- grid[i][j] is either 0 or 1
Explanation
Brute force approach
For every cell, we calculate the difference of zeros and ones. The two nested for-loops will iterate over the array and we calculate the sum as below
diff[i][j] = onesRowi + onesColj - zerosRowi - zerosColjThe time-complexity of this approach is O(n^3).
Using extra space
We can reduce the time-complexity to O(n^2) by using additional two 1D array's. We calculate the count of ones for every row and store it in onesRow array. We do the same for every column and store it in onesCol array.
We then compute the difference using the below approach
diff[i][j] = onesRowi + onesColj - (m - onesRowi) - (n - zerosColj)Let's explore the algorithm.
- set m = grid.size()
n = grid[0].size()
initialize vector<int> onesRow(m, 0)
vector<int> onesCol(n, 0)
i, j
- loop for i = 0; i < m; i++
loop for j = 0; j < n; j++
- if grid[i][j] == 1
- update onesRow[i]++
- if end
- inner for end
- outer for end
- loop for i = 0; i < n; i++
loop for j = 0; j < m; j++
- if grid[j][i] == 1
- update onesCol[i]++
- if end
- inner for end
- outer for end
- initialize vector<vector<int>> diff(m, vector<int>(n))
- loop for i = 0; i < m; i++
loop for j = 0; j < n; j++
- set diff[i][j] = onesRow[i] + onesCol[j] - (m - onesRow[i]) - (n - onesCol[j])
- inner for end
- outer for end
Let's check our algorithm in C++, Golang, and JavaScript.
C++ solution
class Solution {
public:
vector<vector<int>> onesMinusZeros(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<int> onesRow(m, 0);
vector<int> onesCol(n, 0);
int i, j;
for(i = 0; i < m; i++) {
for(j = 0; j < n; j++) {
if(grid[i][j] == 1) {
onesRow[i]++;
}
}
}
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
if(grid[j][i] == 1) {
onesCol[i]++;
}
}
}
vector<vector<int>> diff(m, vector<int>(n));
for(i = 0; i < m; i++) {
for(j = 0; j < n; j++) {
diff[i][j] = onesRow[i] + onesCol[j] - (m - onesRow[i]) - (n - onesCol[j]);
}
}
return diff;
}
};Golang solution
func onesMinusZeros(grid [][]int) [][]int {
m, n := len(grid), len(grid[0])
onesRow := make([]int, m)
onesCol := make([]int, n)
i, j := 0, 0
for i = 0; i < m; i++ {
for j = 0; j < n; j++ {
if grid[i][j] == 1 {
onesRow[i]++
}
}
}
for i = 0; i < n; i++ {
for j = 0; j < m; j++ {
if grid[j][i] == 1 {
onesCol[i]++
}
}
}
diff := make([][]int, m)
for i = 0; i < m; i++ {
diff[i] = make([]int, n)
}
for i = 0; i < m; i++ {
for j = 0; j < n; j++ {
diff[i][j] = onesRow[i] + onesCol[j] - (m - onesRow[i]) - (n - onesCol[j])
}
}
return diff
}JavaScript solution
var onesMinusZeros = function(grid) {
let m = grid.length, n = grid[0].length;
let onesRow = new Array(m).fill(0);
let onesCol = new Array(n).fill(0);
let i, j;
for(i = 0; i < m; i++) {
for(j = 0; j < n; j++) {
if(grid[i][j] === 1) {
onesRow[i]++;
}
}
}
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
if(grid[j][i] === 1) {
onesCol[i]++;
}
}
}
let diff = new Array(m);
for(i = 0; i < m; i++) {
diff[i] = new Array(n);
}
for(i = 0; i < m; i++) {
for(j = 0; j < n; j++) {
diff[i][j] = onesRow[i] + onesCol[j] - (m - onesRow[i]) - (n - onesCol[j]);
}
}
return diff;
};Dry Run
Let's dry-run our algorithm to see how the solution works.
Input: grid = [[0, 1, 1], [1, 0, 1], [0, 0, 1]]
Step 1: m = grid.length
= 3
n = grid[0].length
= 3
onesRow(m, 0)
onesRow = [0, 0, 0]
onesCol(n, 0)
onesCol = [0, 0, 0]
i, j
Step 2: loop for i = 0; i < m; i++
loop for j = 0; j < n; j++
if grid[i][j] == 1
onesRow[i]++
This function will count the number of 1's in each row and set the value in onesRow array.
onesRow = [2, 2, 1]
Step 3: loop for i = 0; i < n; i++
loop for j = 0; j < m; j++
if grid[j][i] == 1
onesCol[i]++
This function will count the number of 1's in each row and set the value in onesRow array.
onesCol = [1, 1, 3]
Step 4: initialize diff(m, vector<int>(n))
diff = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
Step 5: loop for i = 0; i < m; i++
loop for j = 0; j < n; j++
i = 0, j = 0
i < m, j < n
0 < 3, j < 3
true
diff[i][j] = onesRow[i] + onesCol[j] - (m - onesRow[i]) - (n - onesCol[j])
diff[0][0] = onesRow[0] + onesCol[0] - (3 - onesRow[0]) - (3 - onesCol[0])
= 2 + 1 - (3 - 2) - (3 - 1)
= 3 - 1 - 2
= 0
j++
j = 1
Step 6: loop for i = 0; i < m; i++
loop for j = 0; j < n; j++
i < m, j < n
0 < 3, 1 < 3
true
diff[i][j] = onesRow[i] + onesCol[j] - (m - onesRow[i]) - (n - onesCol[j])
diff[0][1] = onesRow[0] + onesCol[1] - (3 - onesRow[0]) - (3 - onesCol[1])
= 2 + 1 - (3 - 2) - (3 - 1)
= 3 - 1 - 2
= 0
j++
j = 2
Step 7: loop for i = 0; i < m; i++
loop for j = 0; j < n; j++
i < m, j < n
0 < 3, 2 < 3
true
diff[i][j] = onesRow[i] + onesCol[j] - (m - onesRow[i]) - (n - onesCol[j])
diff[0][2] = onesRow[0] + onesCol[2] - (3 - onesRow[0]) - (3 - onesCol[2])
= 2 + 3 - (3 - 2) - (3 - 3)
= 5 - 1 - 0
= 4
j++
j = 3
Step 8: loop for i = 0; i < m; i++
loop for j = 0; j < n; j++
i < m, j < n
0 < 3, 3 < 3
false
i++
i = 1
Step 9: loop for i = 0; i < m; i++
loop for j = 0; j < n; j++
i < m, j < n
1 < 3, 0 < 3
true
diff[i][j] = onesRow[i] + onesCol[j] - (m - onesRow[i]) - (n - onesCol[j])
diff[1][0] = onesRow[1] + onesCol[0] - (3 - onesRow[1]) - (3 - onesCol[0])
= 2 + 1 - (3 - 2) - (3 - 1)
= 3 - 1 - 2
= 0
We similarly evaluate for the rest of the cells and return the diff as
[
[0, 0, 4],
[0, 0, 4],
[-2, -2, 2],
]