Difference Between Ones and Zeros in Row and Column

Medium
901.

Difference Between Ones and Zeros in Row and Column

Difference Between Ones and Zeros in Row and Column is a medium coding problem on arrays, matrix and simulation, asked in Amazon, Microsoft and TCS interviews.

For a binary matrix grid, build a matrix diff of the same size where

diff[i][j] = onesRow[i] + onesCol[j] - zerosRow[i] - zerosCol[j]

with onesRow[i] the number of 1s in row i, zerosCol[j] the number of 0s in column j, and so on. Return diff.

Example 1

Input
grid = [[0,1,1],[1,0,1],[0,0,1]]
Output
[[0,0,4],[0,0,4],[-2,-2,2]]

Example 2

Input
grid = [[1,1,1],[1,1,1]]
Output
[[5,5,5],[5,5,5]]
Explanation
Every row has 3 ones and every column 2, so each cell is 3 + 2 - 0 - 0.

Example 3

Input
grid = [[0]]
Output
[[-2]]

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100000
  • 1 <= m · n <= 100000
  • grid[i][j] is 0 or 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number[][]}
 */
var onesMinusZeros = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Difference Between Ones and Zeros in Row and Column Solution

Difference Between Ones and Zeros in Row and Column solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Difference Between Ones and Zeros in Row and Column is a medium coding problem on arrays, matrix and simulation, asked in Amazon, Microsoft and TCS interviews.

  • Difficulty: Medium
  • Topics: Arrays, Matrix, Simulation
  • Asked at: Amazon, Microsoft, TCS
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

For a binary matrix grid, build a matrix diff of the same size where

diff[i][j] = onesRow[i] + onesCol[j] - zerosRow[i] - zerosCol[j]

with onesRow[i] the number of 1s in row i, zerosCol[j] the number of 0s in column j, and so on. Return diff.

Example 1

Input: grid = [[0,1,1],[1,0,1],[0,0,1]]
Output: [[0,0,4],[0,0,4],[-2,-2,2]]

Example 2

Input: grid = [[1,1,1],[1,1,1]]
Output: [[5,5,5],[5,5,5]]
Explanation: Every row has 3 ones and every column 2, so each cell is 3 + 2 - 0 - 0.

Example 3

Input: grid = [[0]]
Output: [[-2]]

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100000
  • 1 <= m · n <= 100000
  • grid[i][j] is 0 or 1

Hints for Difference Between Ones and Zeros in Row and Column

  1. Hint 1

    Every cell's value depends only on its row's and column's one-counts.

  2. Hint 2

    Zeros are the complement: zerosRow[i] = n - onesRow[i] and zerosCol[j] = m - onesCol[j].

  3. Hint 3

    So one pass to tally, then one pass to fill.

How to solve Difference Between Ones and Zeros in Row and Column

Precompute the per-row and per-column one-counts; every cell's answer is then a constant-time expression, with the zero-counts derived as complements.

Approach

  1. Sweep the grid once accumulating onesRow and onesCol.
  2. Fill the output with onesRow[i] + onesCol[j] - (n - onesRow[i]) - (m - onesCol[j]).

Why it works

The formula never refers to the cell itself, only to its line totals — so all m · n answers come from m + n precomputed numbers. Deriving the zero-counts by subtraction avoids a second pair of tallies, and the whole thing stays linear in the grid size.

Complexity

  • Time — O(m · n)
  • Space — O(m + n) beyond the output

Pitfalls

  • Recomputing a row's and column's counts per cell makes it O(m · n · (m + n)).
  • zerosRow[i] uses the row length n, and zerosCol[j] the column height m — swapping them is the classic slip.
  • Values can be negative, which is expected.

Reference solution

Python

from typing import List

def onesMinusZeros(grid: List[List[int]]) -> List[List[int]]:
    m, n = len(grid), len(grid[0])
    row_ones = [sum(r) for r in grid]
    col_ones = [sum(grid[i][j] for i in range(m)) for j in range(n)]
    return [[row_ones[i] + col_ones[j] - (n - row_ones[i]) - (m - col_ones[j])
             for j in range(n)] for i in range(m)]

Java

public static int[][] onesMinusZeros(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] rowOnes = new int[m];
    int[] colOnes = new int[n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            rowOnes[i] += grid[i][j];
            colOnes[j] += grid[i][j];
        }
    }
    int[][] out = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            out[i][j] = rowOnes[i] + colOnes[j] - (n - rowOnes[i]) - (m - colOnes[j]);
        }
    }
    return out;
}

C++

vector<vector<int>> onesMinusZeros(vector<vector<int>>& grid) {
    int m = (int) grid.size(), n = (int) grid[0].size();
    vector<int> rowOnes(m, 0), colOnes(n, 0);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            rowOnes[i] += grid[i][j];
            colOnes[j] += grid[i][j];
        }
    }
    vector<vector<int>> out(m, vector<int>(n, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            out[i][j] = rowOnes[i] + colOnes[j] - (n - rowOnes[i]) - (m - colOnes[j]);
        }
    }
    return out;
}

JavaScript

var onesMinusZeros = function(grid) {
    var m = grid.length, n = grid[0].length, i, j;
    var rowOnes = [], colOnes = [];
    for (i = 0; i < m; i++) rowOnes.push(0);
    for (j = 0; j < n; j++) colOnes.push(0);
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            rowOnes[i] += grid[i][j];
            colOnes[j] += grid[i][j];
        }
    }
    var out = [];
    for (i = 0; i < m; i++) {
        var row = [];
        for (j = 0; j < n; j++) {
            row.push(rowOnes[i] + colOnes[j] - (n - rowOnes[i]) - (m - colOnes[j]));
        }
        out.push(row);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal