# Difference Between Ones and Zeros in Row and Column
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/difference-between-ones-and-zeros-in-row-and-column)
Canonical: https://scaleengineer.com/dsa/problems/difference-between-ones-and-zeros-in-row-and-column
**Data structures:** Array, Matrix
---
## Problem
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`.

**Example 1:**

![](https://assets.glich.co/dsa/difference-between-ones-and-zeros-in-row-and-column/image0.png) 

**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:**

![](https://assets.glich.co/dsa/difference-between-ones-and-zeros-in-row-and-column/image1.png) 

**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 <= 105`
* `1 <= m * n <= 105`
* `grid[i][j]` is either `0` or `1`.

# Approaches
## Brute Force Calculation
This approach directly implements the formula given in the problem statement. For each cell `(i, j)` in the output matrix, it iterates through the corresponding row `i` and column `j` of the input grid to count the number of ones and zeros, and then calculates the difference.
**Time:** O(m * n * (m + n)). For each of the `m * n` cells in the `diff` matrix, we perform a scan of a row (size `n`) and a column (size `m`). This makes the total time complexity prohibitive for the given constraints. · **Space:** O(m * n) to store the output matrix `diff`. The auxiliary space complexity is O(1) as we only use a few variables for counting in the inner loops.
**Pros:** Simple to understand and implement directly from the problem definition.
**Cons:** Highly inefficient due to redundant calculations.; The counts for each row and column are recalculated for every cell in that row/column, leading to a high time complexity.; Will likely result in a 'Time Limit Exceeded' error for larger inputs.
### Explanation
The brute-force approach is a direct translation of the problem description into code. It calculates the value for each cell `diff[i][j]` independently without any optimization or reuse of calculations.

The algorithm is as follows:
1.  Get the dimensions of the grid, `m` (rows) and `n` (columns).
2.  Create a new `m x n` integer matrix called `diff` to store the results.
3.  Use nested loops to iterate through each cell `(i, j)` of the `diff` matrix.
4.  Inside the loops, for the current cell `(i, j)`:
    a.  Initialize counters: `onesRow_i = 0`, `zerosRow_i = 0`, `onesCol_j = 0`, `zerosCol_j = 0`.
    b.  Iterate through the `i`-th row of the `grid` to count `onesRow_i` and `zerosRow_i`.
    c.  Iterate through the `j`-th column of the `grid` to count `onesCol_j` and `zerosCol_j`.
    d.  Calculate `diff[i][j]` using the formula: `onesRow_i + onesCol_j - zerosRow_i - zerosCol_j`.
5.  After iterating through all cells, return the `diff` matrix.

This method is straightforward but highly inefficient because for each cell `(i, j)`, it re-scans the entire row `i` and column `j`.

Here is the implementation in Java:
```java
class Solution {
    public int[][] onesMinusZeros(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] diff = new int[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int onesRow_i = 0;
                int zerosRow_i = 0;
                // Count ones and zeros in row i
                for (int k = 0; k < n; k++) {
                    if (grid[i][k] == 1) {
                        onesRow_i++;
                    } else {
                        zerosRow_i++;
                    }
                }

                int onesCol_j = 0;
                int zerosCol_j = 0;
                // Count ones and zeros in column j
                for (int k = 0; k < m; k++) {
                    if (grid[k][j] == 1) {
                        onesCol_j++;
                    } else {
                        zerosCol_j++;
                    }
                }

                diff[i][j] = onesRow_i + onesCol_j - zerosRow_i - zerosCol_j;
            }
        }
        return diff;
    }
}
```
### Algorithm
* Initialize an `m x n` result matrix `diff`.
* Iterate through each cell `(i, j)` of the `diff` matrix.
* For each `(i, j)`, calculate `onesRow_i`, `zerosRow_i`, `onesCol_j`, and `zerosCol_j` by scanning the `i`-th row and `j`-th column of the input `grid`.
* Compute `diff[i][j] = onesRow_i + onesCol_j - zerosRow_i - zerosCol_j`.
* Return the `diff` matrix.

## Optimized Approach with Pre-computation
This approach optimizes the calculation by first simplifying the formula and then pre-computing the required values. Instead of recalculating row and column sums for each cell, we compute them once and store them in auxiliary arrays. This avoids redundant work.
**Time:** O(m * n). We make two passes over the grid dimensions. The first pass is over the `grid` to compute the counts (`O(m * n)`). The second pass is to fill the `diff` matrix (`O(m * n)`). The total time complexity is linear. · **Space:** O(m * n). We need `O(m + n)` auxiliary space for the `onesRow` and `onesCol` arrays, and `O(m * n)` space for the output `diff` matrix.
**Pros:** Highly efficient with a linear time complexity relative to the number of cells in the grid.; Avoids redundant calculations by pre-computing and storing row and column sums.; Passes all test cases within the time limits.
**Cons:** Requires extra space for the auxiliary arrays to store the row and column counts.
### Explanation
This approach significantly improves performance by avoiding redundant computations. The key idea is to first pre-calculate the number of ones for each row and each column and then use a simplified version of the given formula to construct the difference matrix `diff`.

First, let's simplify the formula:
`diff[i][j] = onesRow_i + onesCol_j - zerosRow_i - zerosCol_j`

We know that for any row `i`, the number of zeros is the total number of columns `n` minus the number of ones:
`zerosRow_i = n - onesRow_i`

Similarly, for any column `j`, the number of zeros is the total number of rows `m` minus the number of ones:
`zerosCol_j = m - onesCol_j`

Substituting these into the original formula:
`diff[i][j] = onesRow_i + onesCol_j - (n - onesRow_i) - (m - onesCol_j)`
`diff[i][j] = onesRow_i + onesCol_j - n + onesRow_i - m + onesCol_j`
`diff[i][j] = 2 * onesRow_i + 2 * onesCol_j - n - m`

This simplified formula is much more efficient to compute once we have the counts of ones for all rows and columns.

The algorithm proceeds as follows:
1.  Create two arrays, `onesRow` of size `m` and `onesCol` of size `n`, to store the counts of ones.
2.  Traverse the input `grid` once. For each cell `grid[i][j]`, if its value is 1, increment `onesRow[i]` and `onesCol[j]`.
3.  After the traversal, `onesRow[i]` will hold the total number of ones in row `i`, and `onesCol[j]` will hold the total number of ones in column `j`.
4.  Create the `diff` matrix of size `m x n`.
5.  Traverse from `i = 0` to `m-1` and `j = 0` to `n-1`, and for each cell `diff[i][j]`, calculate its value using the simplified formula: `diff[i][j] = 2 * onesRow[i] + 2 * onesCol[j] - n - m`.
6.  Return the resulting `diff` matrix.

Here is the implementation in Java:
```java
class Solution {
    public int[][] onesMinusZeros(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int[] onesRow = new int[m];
        int[] onesCol = new int[n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    onesRow[i]++;
                    onesCol[j]++;
                }
            }
        }

        int[][] diff = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // Using the simplified formula:
                // diff[i][j] = 2 * onesRow[i] + 2 * onesCol[j] - n - m
                diff[i][j] = 2 * onesRow[i] + 2 * onesCol[j] - n - m;
            }
        }

        return diff;
    }
}
```
### Algorithm
* First, simplify the formula for `diff[i][j]` to `2 * onesRow_i + 2 * onesCol_j - n - m`.
* Create two arrays, `onesRow` of size `m` and `onesCol` of size `n`, to store the count of ones for each row and column, respectively.
* Iterate through the input `grid` once. For each cell `grid[i][j]` that is 1, increment `onesRow[i]` and `onesCol[j]`.
* Initialize an `m x n` result matrix `diff`.
* Iterate through each cell `(i, j)` of the `diff` matrix.
* Calculate `diff[i][j]` using the pre-computed counts and the simplified formula: `diff[i][j] = 2 * onesRow[i] + 2 * onesCol[j] - m - n`.
* Return the `diff` matrix.

# Solutions
### Java

```java
class Solution {
public
  int[][] onesMinusZeros(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] rows = new int[m];
    int[] cols = new int[n];
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        int v = grid[i][j];
        rows[i] += v;
        cols[j] += v;
      }
    }
    int[][] diff = new int[m][n];
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        diff[i][j] = rows[i] + cols[j] - (n - rows[i]) - (m - cols[j]);
      }
    }
    return diff;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> onesMinusZeros(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    vector<int> rows(m);
    vector<int> cols(n);
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        int v = grid[i][j];
        rows[i] += v;
        cols[j] += v;
      }
    }
    vector<vector<int>> diff(m, vector<int>(n));
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        diff[i][j] = rows[i] + cols[j] - (n - rows[i]) - (m - cols[j]);
      }
    }
    return diff;
  }
};

```

### Python

```python
class Solution:
    def onesMinusZeros(self, grid: List[List[int]]) -> List[List[int]]: m, n = len(grid), len(grid[0]) rows = [0] * m cols = [0] * n for i, row in enumerate(grid): for j, v in enumerate(row): rows[i] += v cols[j] += v diff = [[0] * n for _ in range(m)] for i, r in enumerate(rows): for j, c in enumerate(cols): diff[i][j] = r + c - (n - r) - (m - c) return diff

```