LeetCode 2482 - Difference Between Ones and Zeros in Row and Column

The problem gives us a binary matrix grid with m rows and n columns. Every cell contains either 0 or 1. We must construct another matrix called diff, where each position diff[i][j] depends on how many ones and zeros appear in row i and column j.

leetcodemediumarraymatrixsimulation

LeetCode Problem 2482

Difficulty: 🟡 Medium
Topics: Array, Matrix, Simulation

Solution

LeetCode 2482 - Difference Between Ones and Zeros in Row and Column

Problem Understanding

The problem gives us a binary matrix grid with m rows and n columns. Every cell contains either 0 or 1. We must construct another matrix called diff, where each position diff[i][j] depends on how many ones and zeros appear in row i and column j.

For every cell (i, j), we compute:

$$\text{diff}[i][j] = \text{onesRow}_i + \text{onesCol}_j - \text{zerosRow}_i - \text{zerosCol}_j$$

This means each cell is determined entirely by four counts:

  • Number of ones in its row
  • Number of ones in its column
  • Number of zeros in its row
  • Number of zeros in its column

The input matrix itself never changes. We only use it to gather statistics about rows and columns.

The constraints are important:

  • 1 <= m, n <= 10^5
  • 1 <= m * n <= 10^5

The product m * n is at most 100000, which means the total number of cells is manageable. However, repeatedly scanning rows and columns for every cell would still be inefficient.

A naive implementation could easily become too slow if it recomputes row and column counts for every matrix position separately.

There are several important edge cases:

  • A matrix with all ones
  • A matrix with all zeros
  • A single row matrix
  • A single column matrix
  • Very rectangular matrices such as 1 x 100000 or 100000 x 1

The problem guarantees that every value is either 0 or 1, so we never need to handle invalid data.

Approaches

Brute Force Approach

The most direct solution is to compute each diff[i][j] independently.

For every cell (i, j):

  1. Scan row i and count ones and zeros.
  2. Scan column j and count ones and zeros.
  3. Apply the formula.

This approach is correct because every cell receives exactly the values required by the definition.

However, this is inefficient. For every cell, we scan an entire row and an entire column.

If there are m * n cells, and each calculation takes O(m + n), the total complexity becomes:

$$O(m \cdot n \cdot (m + n))$$

This is too slow for the maximum constraints.

Optimal Approach

The key observation is that row and column counts are reused repeatedly.

For example:

  • Every cell in the same row shares the same onesRow and zerosRow.
  • Every cell in the same column shares the same onesCol and zerosCol.

Instead of recomputing these counts many times, we can precompute them once.

We create:

  • rowOnes[i] = number of ones in row i
  • colOnes[j] = number of ones in column j

Then:

$$\text{zerosRow}_i = n - \text{rowOnes}_i$$

$$\text{zerosCol}_j = m - \text{colOnes}_j$$

Substituting into the formula:

$$\text{diff}[i][j] = \text{rowOnes}[i] + \text{colOnes}[j] - (n - \text{rowOnes}[i]) - (m - \text{colOnes}[j])$$

Simplifying:

$$\text{diff}[i][j] = 2 \cdot \text{rowOnes}[i] + 2 \cdot \text{colOnes}[j] - n - m$$

Now every cell can be computed in constant time after preprocessing.

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n * (m + n)) O(1) Recomputes row and column counts repeatedly
Optimal O(m * n) O(m + n) Precomputes row and column statistics once

Algorithm Walkthrough

  1. Determine the matrix dimensions m and n.
  2. Create two arrays:
  • rowOnes of size m
  • colOnes of size n

These arrays store how many ones appear in each row and column. 3. Traverse the matrix once.

For every cell (i, j):

  • If grid[i][j] == 1

  • Increment rowOnes[i]

  • Increment colOnes[j]

After this pass, we know the number of ones in every row and column. 4. Create the result matrix diff. 5. Traverse the matrix again.

For each cell (i, j):

  • Compute zeros in the row:

$$zerosRow = n - rowOnes[i]$$

  • Compute zeros in the column:

$$zerosCol = m - colOnes[j]$$

  • Apply the formula:

$$diff[i][j] = rowOnes[i] + colOnes[j] - zerosRow - zerosCol$$ 6. Return the completed diff matrix.

Why it works

The algorithm works because every diff[i][j] depends only on aggregate information about row i and column j. By preprocessing these aggregates once, we avoid redundant computation.

The counts stored in rowOnes and colOnes are exact, and zeros are derived directly from matrix dimensions. Therefore every computed cell matches the definition from the problem statement.

Python Solution

from typing import List

class Solution:
    def onesMinusZeros(self, grid: List[List[int]]) -> List[List[int]]:
        m = len(grid)
        n = len(grid[0])

        row_ones = [0] * m
        col_ones = [0] * n

        # Count ones in rows and columns
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    row_ones[i] += 1
                    col_ones[j] += 1

        # Build result matrix
        diff = [[0] * n for _ in range(m)]

        for i in range(m):
            for j in range(n):
                zeros_row = n - row_ones[i]
                zeros_col = m - col_ones[j]

                diff[i][j] = (
                    row_ones[i]
                    + col_ones[j]
                    - zeros_row
                    - zeros_col
                )

        return diff

The implementation begins by determining the matrix dimensions. This is necessary because row and column sizes are used repeatedly when calculating zero counts.

The arrays row_ones and col_ones store the number of ones in every row and column. The first nested loop fills these arrays in a single traversal of the matrix.

The second nested loop constructs the final answer matrix. For every cell, the number of zeros is derived mathematically instead of counted explicitly. This avoids unnecessary work and keeps the solution linear in the number of cells.

The algorithm never modifies the input matrix, and every value is computed independently using the preprocessed statistics.

Go Solution

func onesMinusZeros(grid [][]int) [][]int {
    m := len(grid)
    n := len(grid[0])

    rowOnes := make([]int, m)
    colOnes := make([]int, n)

    // Count ones in rows and columns
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                rowOnes[i]++
                colOnes[j]++
            }
        }
    }

    // Build result matrix
    diff := make([][]int, m)

    for i := 0; i < m; i++ {
        diff[i] = make([]int, n)

        for j := 0; j < n; j++ {
            zerosRow := n - rowOnes[i]
            zerosCol := m - colOnes[j]

            diff[i][j] = rowOnes[i] +
                colOnes[j] -
                zerosRow -
                zerosCol
        }
    }

    return diff
}

The Go implementation follows exactly the same logic as the Python version. Slices are used for dynamic arrays, and the result matrix is allocated row by row.

Integer overflow is not a concern because the maximum possible value is bounded by m + n, which is at most 200000.

Go requires explicit matrix allocation, so each row of diff is initialized individually.

Worked Examples

Example 1

grid =
[
  [0,1,1],
  [1,0,1],
  [0,0,1]
]

Step 1: Count Ones

Row Ones Count
0 2
1 2
2 1

So:

rowOnes = [2, 2, 1]

Step 2: Count Column Ones

Column Ones Count
0 1
1 1
2 3

So:

colOnes = [1, 1, 3]

Step 3: Compute Each Cell

For (0,0):

onesRow = 2
onesCol = 1
zerosRow = 1
zerosCol = 2

diff[0][0] = 2 + 1 - 1 - 2 = 0

For (0,2):

onesRow = 2
onesCol = 3
zerosRow = 1
zerosCol = 0

diff[0][2] = 2 + 3 - 1 - 0 = 4

Continuing similarly for all cells:

Cell Value
(0,0) 0
(0,1) 0
(0,2) 4
(1,0) 0
(1,1) 0
(1,2) 4
(2,0) -2
(2,1) -2
(2,2) 2

Final result:

[
  [0,0,4],
  [0,0,4],
  [-2,-2,2]
]

Example 2

grid =
[
  [1,1,1],
  [1,1,1]
]

Step 1: Row Counts

rowOnes = [3, 3]

Step 2: Column Counts

colOnes = [2, 2, 2]

Step 3: Compute Values

For every cell:

onesRow = 3
onesCol = 2
zerosRow = 0
zerosCol = 0

diff = 3 + 2 - 0 - 0 = 5

Final matrix:

[
  [5,5,5],
  [5,5,5]
]

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Every cell is visited a constant number of times
Space O(m + n) Stores row and column counts

The algorithm performs two complete traversals of the matrix. Since the matrix contains m * n cells, the total runtime is linear in the input size.

The extra memory comes from storing row counts and column counts. The output matrix itself is not counted as auxiliary space because it is required by the problem.

Test Cases

from typing import List

class Solution:
    def onesMinusZeros(self, grid: List[List[int]]) -> List[List[int]]:
        m = len(grid)
        n = len(grid[0])

        row_ones = [0] * m
        col_ones = [0] * n

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    row_ones[i] += 1
                    col_ones[j] += 1

        diff = [[0] * n for _ in range(m)]

        for i in range(m):
            for j in range(n):
                zeros_row = n - row_ones[i]
                zeros_col = m - col_ones[j]

                diff[i][j] = (
                    row_ones[i]
                    + col_ones[j]
                    - zeros_row
                    - zeros_col
                )

        return diff

sol = Solution()

# Example 1
assert sol.onesMinusZeros([
    [0,1,1],
    [1,0,1],
    [0,0,1]
]) == [
    [0,0,4],
    [0,0,4],
    [-2,-2,2]
]

# Example 2, all ones
assert sol.onesMinusZeros([
    [1,1,1],
    [1,1,1]
]) == [
    [5,5,5],
    [5,5,5]
]

# Single cell with zero
assert sol.onesMinusZeros([
    [0]
]) == [[-2]]

# Single cell with one
assert sol.onesMinusZeros([
    [1]
]) == [[2]]

# All zeros matrix
assert sol.onesMinusZeros([
    [0,0],
    [0,0]
]) == [
    [-4,-4],
    [-4,-4]
]

# Single row
assert sol.onesMinusZeros([
    [1,0,1,0]
]) == [
    [1,1,1,1]
]

# Single column
assert sol.onesMinusZeros([
    [1],
    [0],
    [1]
]) == [
    [2],
    [0],
    [2]
]

# Rectangular matrix
assert sol.onesMinusZeros([
    [1,0,0],
    [0,1,1]
]) == [
    [-1,1,1],
    [1,3,3]
]
Test Why
Example 1 Validates standard mixed matrix behavior
Example 2 Validates all ones scenario
Single cell zero Smallest possible input with minimum counts
Single cell one Smallest possible input with maximum counts
All zeros matrix Ensures negative values are handled correctly
Single row Tests row-heavy structure
Single column Tests column-heavy structure
Rectangular matrix Validates non-square matrices

Edge Cases

Single Cell Matrix

A 1 x 1 matrix is the smallest possible input. This case can expose mistakes involving dimensions or index handling. For example, a solution that assumes multiple rows or columns may fail.

The implementation handles this naturally because row and column counts are still computed correctly, even when both dimensions equal one.

All Zeros Matrix

When every cell is zero, all one counts become zero and all zero counts become maximal. This produces negative values throughout the result matrix.

Some incorrect implementations accidentally assume results are always non-negative. The provided solution follows the exact formula and correctly handles negative outputs.

Highly Rectangular Matrices

The constraints allow matrices like 1 x 100000 or 100000 x 1. These shapes can expose inefficiencies in algorithms that repeatedly scan rows or columns.

The optimized solution remains efficient because each cell is processed only a constant number of times. The runtime stays linear in the total number of cells.

All Ones Matrix

If every value is one, then zero counts become zero everywhere. This tests whether the implementation correctly derives zeros using dimensions rather than explicitly counting them.

The algorithm computes:

$$zerosRow = n - rowOnes[i]$$

and

$$zerosCol = m - colOnes[j]$$

which correctly becomes zero in this scenario.