Skip to main content
Talentd

Difference Between Ones and Zeros in Row and Column - Solution & Explanation

MediumArrayMatrixSimulation20 min readAsked at: Amazon
Practice this problem

Problem Statement

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:

Input: grid = [[0,1,1],[1,0,1],[0,0,1]]
Output: [[0,0,4],[0,0,4],[-2,-2,2]]
Explanation:
- diff[0][0] = onesRow0 + onesCol0 - zerosRow0 - zerosCol0 = 2 + 1 - 1 - 2 = 0 
- diff[0][1] = onesRow0 + onesCol1 - zerosRow0 - zerosCol1 = 2 + 1 - 1 - 2 = 0 
- diff[0][2] = onesRow0 + onesCol2 - zerosRow0 - zerosCol2 = 2 + 3 - 1 - 0 = 4 
- diff[1][0] = onesRow1 + onesCol0 - zerosRow1 - zerosCol0 = 2 + 1 - 1 - 2 = 0 
- diff[1][1] = onesRow1 + onesCol1 - zerosRow1 - zerosCol1 = 2 + 1 - 1 - 2 = 0 
- diff[1][2] = onesRow1 + onesCol2 - zerosRow1 - zerosCol2 = 2 + 3 - 1 - 0 = 4 
- diff[2][0] = onesRow2 + onesCol0 - zerosRow2 - zerosCol0 = 1 + 1 - 2 - 2 = -2
- diff[2][1] = onesRow2 + onesCol1 - zerosRow2 - zerosCol1 = 1 + 1 - 2 - 2 = -2
- diff[2][2] = onesRow2 + onesCol2 - zerosRow2 - zerosCol2 = 1 + 3 - 2 - 0 = 2

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.

Approach Overview

Problem Overview: You are given a binary m x n grid. For each cell (i, j), compute the difference between the number of ones and zeros in its row and column combined. Formally, diff[i][j] = onesRow[i] + onesCol[j] - zerosRow[i] - zerosCol[j]. The task is to build the resulting matrix efficiently.

Approach 1: Precompute Row and Column Counts (Time: O(m*n), Space: O(m+n))

The straightforward strategy is to count how many 1s appear in every row and every column first. Iterate through the grid once to populate two arrays: rowOnes[m] and colOnes[n]. Since each row has n elements and each column has m, you can derive zeros using zerosRow = n - rowOnes[i] and zerosCol = m - colOnes[j]. Then iterate through the grid again and compute the difference for each cell using the formula. This approach is easy to reason about and keeps the logic clean because counting and result computation are separated. It’s a common technique when working with matrix problems that require repeated row/column statistics.

Approach 2: Optimized Counting in Single Pass (Time: O(m*n), Space: O(m+n))

You can slightly streamline the counting by collecting row and column counts during a single traversal of the grid. While iterating through every cell, increment rowOnes[i] and colOnes[j] whenever a 1 is encountered. After this pass, compute each result cell using a simplified formula: diff[i][j] = 2 * rowOnes[i] + 2 * colOnes[j] - m - n. This works because zerosRow = n - rowOnes and zerosCol = m - colOnes. The formula avoids explicitly computing zeros and reduces arithmetic per cell. The approach still runs in linear time relative to the grid size and is typical for problems involving aggregated counts in arrays and simulation style transformations.

Recommended for interviews: The precompute row/column counts approach is what most interviewers expect. It clearly demonstrates that you recognize repeated computations and replace them with cached counts. The optimized formula version shows deeper understanding of the relationship between ones and zeros and reduces redundant calculations while keeping the same O(m*n) complexity.

Approach 1: Precompute Row and Column Counts

This approach involves counting the number of ones and zeros in each row and each column beforehand. Then, for each element in the grid, compute the corresponding value in the difference matrix using the precomputed counts.

In this C solution, we first initialize arrays to store the count of ones and zeros for each row and column. We iterate over the grid to fill these arrays. Then, we calculate the difference matrix using these precomputed values. Finally, the result is returned as a dynamically allocated 2D array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns. This involves going through each element of the grid twice; once for counting and once for filling the difference matrix.
Space Complexity: O(m + n) for storing counts of ones and zeros for each row and column.

Try this approach in the editor →

Approach 2: Optimized Counting in Single Pass

This approach seeks to optimize the space complexity by calculating necessary counts and the result matrix in a single pass, thereby avoiding separate storage for ones and zeros counts.

In this C implementation, we reduce memory usage by calculating the difference matrix directly in a single pass after counting column ones. This avoids storing all separate zero counts, optimizing space complexity.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n) because every element is iterated over during the counting and result generation stages.
Space Complexity: O(n) due to the storage of column ones, improving from O(m + n).

Try this approach in the editor →

Approach 3: Simulation

We can solve this problem by simulating the process as described in the problem statement.

The time complexity is O(m times n), and if we ignore the space used by the answer, the space complexity is O(m + n). Here, m and n are the number of rows and columns in the matrix, respectively.

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Precompute Row and Column Counts

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns. This involves going through each element of the grid twice; once for counting and once for filling the difference matrix.
Space Complexity: O(m + n) for storing counts of ones and zeros for each row and column.

Optimized Counting in Single Pass

Time Complexity: O(m * n) because every element is iterated over during the counting and result generation stages.
Space Complexity: O(n) due to the storage of column ones, improving from O(m + n).

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Precompute Row and Column CountsO(m*n)O(m+n)Best general solution. Easy to implement and clearly separates counting and result construction.
Optimized Counting with Derived FormulaO(m*n)O(m+n)Preferred when simplifying arithmetic and reducing repeated calculations using the derived formula.

Video Solution

Difference Between Ones and Zeros in Row and Column | Intuition | Leetcode-2482 • codestorywithMIK • 3,893 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Difference Between Ones and Zeros in Row and Column easy or hard?
The problem is rated Medium on LeetCode but conceptually straightforward once you recognize that row and column counts can be reused. The main challenge is identifying the formula that combines row and column ones and zeros efficiently without recomputing counts for every cell.
Difference Between Ones and Zeros in Row and Column Python/Java solution
Python and Java implementations follow the same idea: compute rowOnes and colOnes arrays, then build the result matrix using the derived formula. Python typically uses list comprehensions or nested loops, while Java uses integer arrays and standard for-loops. Both implementations run in O(m*n) time and O(m+n) space.
How to solve Difference Between Ones and Zeros in Row and Column in O(n)?
Treat the matrix size as m*n elements and solve it in linear time relative to the grid size. Count ones in each row and column during a traversal, then compute each cell using the formula diff[i][j] = 2*rowOnes[i] + 2*colOnes[j] - m - n. This avoids recalculating counts for every cell and keeps the algorithm O(m*n).
What is the best approach for Difference Between Ones and Zeros in Row and Column?
The best approach precomputes the number of ones in every row and column. After collecting rowOnes and colOnes in O(m*n) time, each cell’s difference can be computed directly using a constant-time formula. This avoids recomputing row and column counts repeatedly and keeps the overall complexity linear in the size of the grid.
Is Difference Between Ones and Zeros in Row and Column asked at Google/Amazon/Meta?
Matrix counting and row/column aggregation problems are common across companies like Google, Amazon, and Meta. Variants that require precomputing row or column statistics appear frequently because they test grid traversal, space optimization, and recognizing reusable computations.
What data structure is used in Difference Between Ones and Zeros in Row and Column?
The solution primarily uses arrays to store row and column counts. Two auxiliary arrays, rowOnes and colOnes, track how many ones appear in each row and column. The final answer is stored in another matrix of the same size as the input grid.
What is the time complexity of Difference Between Ones and Zeros in Row and Column?
The optimal solution runs in O(m*n) time where m is the number of rows and n is the number of columns. One pass gathers row and column counts, and another pass builds the result matrix. Space complexity is O(m+n) for the auxiliary row and column arrays.

Ready to solve this problem?

Practice Difference Between Ones and Zeros in Row and Column with our built-in code editor and test cases.

Practice on FleetCode
Previous

01 Matrix

Next

First Completely Painted Row or Column