Ones Zeros Difference Grid LeetCode 2482

LeetCode 2482 — Difference Between Ones and Zeros in Row and Column — gives you an m×n binary matrix grid and asks you to return an m×n difference matrix diff where diff[i][j] = onesRow_i + onesCol_j - zerosRow_i - zerosCol_j. Here onesRow_i is the count of ones in row i, zerosRow_i is the count of zeros in row i, onesCol_j is the count of ones in column j, and zerosCol_j is the count of zeros in column j.

The problem is rated Medium and the constraint is up to 10^5 cells total, so an O(m*n) solution with minimal extra space is expected. A naive approach that recomputes row and column sums for every cell would also be O(m*n) in practice, but reusing precomputed arrays makes the code clean and easy to reason about.

Understanding the formula is the key step. Once you realize that zeros = length - ones for both rows and columns, you can simplify diff[i][j] to a formula that only requires two precomputed arrays — one for row ones counts and one for column ones counts.

The first step is to compute onesRow — an array of length m where onesRow[i] is the sum of all elements in row i of the grid. Since each cell is 0 or 1, summing a row gives exactly the count of ones. zerosRow[i] then equals n - onesRow[i] because each row has exactly n cells.

Similarly, compute onesCol — an array of length n where onesCol[j] is the sum of all elements in column j. zerosCol[j] equals m - onesCol[j] because each column has exactly m cells. There is no need to allocate separate zerosRow or zerosCol arrays; you can compute the zeros counts on the fly using the row and column lengths.

In Python, onesRow = [sum(row) for row in grid] is a single list comprehension. For onesCol, you iterate over each column index j and sum grid[i][j] for all i, or use sum(row[j] for row in grid). Both run in O(m*n) total across all columns.

The algorithm has three straightforward steps that together run in O(m*n) time and use O(m+n) extra space beyond the output matrix. The output matrix itself is O(m*n) but is required by the problem, so it is not counted as extra space.

Building onesRow takes O(m*n) because you sum each of the m rows of length n. Building onesCol takes O(m*n) because you sum each of the n columns of length m. Finally, filling the diff matrix is a nested loop of m*n iterations each doing O(1) work with the precomputed arrays.

The overall time complexity is O(m*n) and space complexity is O(m+n) for the two precomputed arrays. This is optimal — you must read every cell at least once, so O(m*n) is a lower bound.

The raw formula is diff[i][j] = onesRow[i] + onesCol[j] - zerosRow[i] - zerosCol[j]. Substituting zerosRow[i] = n - onesRow[i] and zerosCol[j] = m - onesCol[j] gives: diff[i][j] = onesRow[i] + onesCol[j] - (n - onesRow[i]) - (m - onesCol[j]). Expanding: diff[i][j] = onesRow[i] + onesCol[j] - n + onesRow[i] - m + onesCol[j] = 2*onesRow[i] + 2*onesCol[j] - m - n.

This simplification is important because it removes the need to store or compute zerosRow and zerosCol arrays. Instead of four arrays you only need two. The constants m and n are subtracted uniformly from every cell, which means the relative ordering of diff values is entirely determined by 2*onesRow[i] + 2*onesCol[j].

An equivalent way to see it: the diff at any cell is twice the sum of row ones and column ones, shifted down by the total number of cells in a column plus a row. Cells in rows and columns with many ones will have large positive diff values; cells in sparse rows and columns can have negative diff values.

Consider grid = [[0,1,1],[1,0,1],[0,0,1]]. This is a 3×3 matrix so m = 3, n = 3. First compute onesRow: row 0 has [0,1,1] → sum = 2; row 1 has [1,0,1] → sum = 2; row 2 has [0,0,1] → sum = 1. So onesRow = [2, 2, 1].

Next compute onesCol: column 0 has values [0,1,0] → sum = 1; column 1 has [1,0,0] → sum = 1; column 2 has [1,1,1] → sum = 3. So onesCol = [1, 1, 3]. Now apply the formula diff[i][j] = 2*onesRow[i] + 2*onesCol[j] - 3 - 3 = 2*onesRow[i] + 2*onesCol[j] - 6.

Sample cells: diff[0][0] = 2*2 + 2*1 - 6 = 4 + 2 - 6 = 0; diff[0][2] = 2*2 + 2*3 - 6 = 4 + 6 - 6 = 4; diff[1][2] = 2*2 + 2*3 - 6 = 4; diff[2][0] = 2*1 + 2*1 - 6 = -2; diff[2][2] = 2*1 + 2*3 - 6 = 2.

Python solution using list comprehensions: onesRow = [sum(row) for row in grid]; onesCol = [sum(grid[i][j] for i in range(m)) for j in range(n)]; return [[2*onesRow[i] + 2*onesCol[j] - m - n for j in range(n)] for i in range(m)]. This is three lines and runs in O(m*n) time, O(m+n) extra space.

Java solution: int[] onesRow = new int[m]; for(int i=0;i<m;i++) for(int j=0;j<n;j++) onesRow[i]+=grid[i][j]; int[] onesCol = new int[n]; for(int i=0;i<m;i++) for(int j=0;j<n;j++) onesCol[j]+=grid[i][j]; then fill int[][] diff = new int[m][n]; for(int i=0;i<m;i++) for(int j=0;j<n;j++) diff[i][j]=2*onesRow[i]+2*onesCol[j]-m-n; return diff;.

Both solutions share the same O(m*n) time and O(m+n) extra space characteristics. The Python version benefits from built-in sum and list comprehension syntax for concise column summation. The Java version uses two explicit nested loops for clarity and avoids boxing overhead.

LeetCode 2482 belongs to the matrix precomputation family. Equal Row and Column Pairs (LeetCode 2352) also involves analyzing rows and columns independently — you count pairs (r, c) where row r equals column c, using hash maps of row and column tuples. Set Matrix Zeroes (LeetCode 73) precomputes which rows and columns need to be zeroed, then applies the mutation in a second pass — the same two-phase pattern used here.

01 Matrix (LeetCode 542) uses BFS from all zeros simultaneously to fill a distance matrix, which is a different technique but has the same flavor of computing a value at every cell based on a global property of the grid. The game of life (LeetCode 289) is another grid problem where precomputing neighbor counts before mutating avoids read-after-write corruption.

The general lesson from this family: when the value at each cell depends only on aggregate row and column properties (sums, counts, presence of a value), precompute those aggregates in linear sweeps, then fill the output matrix in a final pass. This pattern keeps both time complexity and code complexity minimal.