Scale Engineer

Difference Between Ones and Zeros in Row and Column

Med
#2264Time: 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.
Data structures
ArrayMatrix

Prompt

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:

onesRow<sub>0</sub> + onesCol<sub>0</sub> - zerosRow<sub>0</sub> - zerosCol<sub>0</sub>

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

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

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;    }}

Complexity

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.

Trade-offs

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.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem