Difference Between Ones and Zeros in Row and Column — Medium Problem & Solution

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

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)]

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium