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 `ith` row be `onesRowi`.

• Let the number of ones in the `jth` column be `onesColj`.

• Let the number of zeros in the `ith` row be `zerosRowi`.

• Let the number of zeros in the `jth` column be `zerosColj`.

• `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 - zerosColj``

The 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],
]
``````