Difference Between Ones and Zeros in Row and Column solution and explanation
9 more videos on this problem
Difference Between Ones and Zeros in Row and Column | Intuition | Leetcode-2482codestorywithMIK · 12:46 · 3K views
✅ Difference Between Ones and Zeros in Row and Column - Elegant - 2D Arrays - Matrix - LeetCode 2482Leet Logics · 10:15 · 993 views
Leetcode | 2482. Difference Between Ones and Zeros in Row and Column | Medium | Java SolutionDeveloper Docs · 12:28 · 645 views
Leetcode 2482: Difference Between Ones and Zeros in Row and ColumnAlgorithms Casts · 6:49 · 434 views
2482. Difference Between Ones and Zeros in Row and Column (Leetcode Medium)Programming Live with Larry · 5:48 · 396 views
Solving LeetCode 2482 Difference Between Ones and Zeros in Row and Column | Array | AmazonCode Harmony · 9:29 · 381 views
2482. Difference Between Ones and Zeros in Row and Column - LeetCode POTD | JavaAkshay Anil · 6:32 · 328 views
2482. Difference Between Ones and Zeros in Row and Column - LeetCode SQL SolutionCode with Carter · 11:41 · 290 views
Leetcode: 2482. Difference Between Ones and Zeros in Row and Column ExplainedYou code with Dmytro · 6:51 · 129 views
Difference Between Ones and Zeroes in Row and Column - LeetCode 2482 - PythonAlpha-Code · 9:49 · 94 views
The problem
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
ithrow beonesRowi. - Let the number of ones in the
jthcolumn beonesColj. - Let the number of zeros in the
ithrow bezerosRowi. - Let the number of zeros in the
jthcolumn bezerosColj. 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.lengthn == grid[i].length1 <= m, n <= 1051 <= m * n <= 105grid[i][j]is either0or1.
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.
def difference_matrix(grid):
m, n = len(grid), len(grid[0])
ones_row = [0] * m
zeros_row = [0] * m
ones_col = [0] * n
zeros_col = [0] * n
# Precompute the number of ones and zeros in each row and column
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
ones_row[i] += 1
ones_col[j] += 1
else:
zeros_row[i] += 1
zeros_col[j] += 1
diff = [[0] * n for _ in range(m)]
# Create the difference matrix
for i in range(m):
for j in range(n):
diff[i][j] = ones_row[i] + ones_col[j] - zeros_row[i] - zeros_col[j]
return diffimport java.util.*;
class Solution {
public int[][] differenceMatrix(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[] onesRow = new int[m];
int[] zerosRow = new int[m];
int[] onesCol = new int[n];
int[] zerosCol = new int[n];
// Precompute the number of ones and zeros in each row and column
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
onesRow[i]++;
onesCol[j]++;
} else {
zerosRow[i]++;
zerosCol[j]++;
}
}
}
int[][] diff = new int[m][n];
// Create the difference matrix
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
diff[i][j] = onesRow[i] + onesCol[j] - zerosRow[i] - zerosCol[j];
}
}
return diff;
}
}#include <vector>
std::vector<std::vector<int>> differenceMatrix(std::vector<std::vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
std::vector<int> onesRow(m, 0);
std::vector<int> zerosRow(m, 0);
std::vector<int> onesCol(n, 0);
std::vector<int> zerosCol(n, 0);
// Precompute the number of ones and zeros in each row and column
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
onesRow[i]++;
onesCol[j]++;
} else {
zerosRow[i]++;
zerosCol[j]++;
}
}
}
std::vector<std::vector<int>> diff(m, std::vector<int>(n, 0));
// Create the difference matrix
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
diff[i][j] = onesRow[i] + onesCol[j] - zerosRow[i] - zerosCol[j];
}
}
return diff;
}function differenceMatrix(grid) {
const m = grid.length;
const n = grid[0].length;
const onesRow = new Array(m).fill(0);
const zerosRow = new Array(m).fill(0);
const onesCol = new Array(n).fill(0);
const zerosCol = new Array(n).fill(0);
// Precompute the number of ones and zeros in each row and column
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
onesRow[i]++;
onesCol[j]++;
} else {
zerosRow[i]++;
zerosCol[j]++;
}
}
}
const diff = Array.from({ length: m }, () => new Array(n).fill(0));
// Create the difference matrix
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
diff[i][j] = onesRow[i] + onesCol[j] - zerosRow[i] - zerosCol[j];
}
}
return diff;
}#include <stdio.h>
#include <stdlib.h>
int** differenceMatrix(int** grid, int gridSize, int* gridColSize, int* returnSize, int** returnColumnSizes) {
int* onesRow = (int*)calloc(gridSize, sizeof(int));
int* zerosRow = (int*)calloc(gridSize, sizeof(int));
int* onesCol = (int*)calloc(gridColSize[0], sizeof(int));
int* zerosCol = (int*)calloc(gridColSize[0], sizeof(int));
// Precompute the number of ones and zeros in each row and column
for (int i = 0; i < gridSize; i++) {
for (int j = 0; j < gridColSize[i]; j++) {
if (grid[i][j] == 1) {
onesRow[i]++;
onesCol[j]++;
} else {
zerosRow[i]++;
zerosCol[j]++;
}
}
}
// Create the difference matrix
int** diff = (int**)malloc(gridSize * sizeof(int*));
*returnSize = gridSize;
*returnColumnSizes = (int*)malloc(gridSize * sizeof(int));
for (int i = 0; i < gridSize; i++) {
(*returnColumnSizes)[i] = gridColSize[i];
diff[i] = (int*)malloc(gridColSize[i] * sizeof(int));
for (int j = 0; j < gridColSize[i]; j++) {
diff[i][j] = onesRow[i] + onesCol[j] - zerosRow[i] - zerosCol[j];
}
}
free(onesRow);
free(zerosRow);
free(onesCol);
free(zerosCol);
return diff;
}using System;
public class Solution {
public int[][] DifferenceMatrix(int[][] grid) {
int m = grid.Length;
int n = grid[0].Length;
int[] onesRow = new int[m];
int[] zerosRow = new int[m];
int[] onesCol = new int[n];
int[] zerosCol = new int[n];
// Precompute the number of ones and zeros in each row and column
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
onesRow[i]++;
onesCol[j]++;
} else {
zerosRow[i]++;
zerosCol[j]++;
}
}
}
int[][] diff = new int[m][];
// Create the difference matrix
for (int i = 0; i < m; i++) {
diff[i] = new int[n];
for (int j = 0; j < n; j++) {
diff[i][j] = onesRow[i] + onesCol[j] - zerosRow[i] - zerosCol[j];
}
}
return diff;
}
}The Python solution effectively uses lists to precompute the number of ones and zeros. The difference matrix is then calculated for each element in the grid leveraging these precomputed values, aligning with a straightforward but efficient approach.
Time Complexity: O(m * n) based on iterating through each element of the grid.
Space Complexity: O(m + n) for storing precomputed row and column counts.
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.
def difference_matrix_single_pass(grid):
m, n = len(grid), len(grid[0])
diff = [[0] * n for _ in range(m)]
ones_col = [0] * n
# Calculate the number of ones in each column
for j in range(n):
for i in range(m):
if grid[i][j] == 1:
ones_col[j] += 1
for i in range(m):
ones_row = sum(grid[i])
zeros_row = n - ones_row
for j in range(n):
zeros_col = m - ones_col[j]
diff[i][j] = ones_row + ones_col[j] - zeros_row - zeros_col
return diffclass Solution {
public int[][] differenceMatrixSinglePass(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] diff = new int[m][n];
int[] onesCol = new int[n];
// Calculate the number of ones in each column
for (int j = 0; j < n; j++) {
for (int i = 0; i < m; i++) {
if (grid[i][j] == 1) {
onesCol[j]++;
}
}
}
for (int i = 0; i < m; i++) {
int onesRow = 0;
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
onesRow++;
}
}
int zerosRow = n - onesRow;
for (int j = 0; j < n; j++) {
int zerosCol = m - onesCol[j];
diff[i][j] = onesRow + onesCol[j] - zerosRow - zerosCol;
}
}
return diff;
}
}#include <vector>
std::vector<std::vector<int>> differenceMatrixSinglePass(std::vector<std::vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
std::vector<std::vector<int>> diff(m, std::vector<int>(n, 0));
std::vector<int> onesCol(n, 0);
// Calculate ones in each column
for (int j = 0; j < n; ++j) {
for (int i = 0; i < m; ++i) {
if (grid[i][j] == 1) {
onesCol[j]++;
}
}
}
for (int i = 0; i < m; ++i) {
int onesRow = 0;
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1) {
onesRow++;
}
}
int zerosRow = n - onesRow;
for (int j = 0; j < n; ++j) {
int zerosCol = m - onesCol[j];
diff[i][j] = onesRow + onesCol[j] - zerosRow - zerosCol;
}
}
return diff;
}function differenceMatrixSinglePass(grid) {
const m = grid.length;
const n = grid[0].length;
const diff = Array.from({ length: m }, () => new Array(n).fill(0));
const onesCol = new Array(n).fill(0);
// Calculate the number of ones in each column
for (let j = 0; j < n; j++) {
let sum = 0;
for (let i = 0; i < m; i++) {
sum += grid[i][j];
}
onesCol[j] = sum;
}
for (let i = 0; i < m; i++) {
const onesRow = grid[i].reduce((a, b) => a + b, 0);
const zerosRow = n - onesRow;
for (let j = 0; j < n; j++) {
const zerosCol = m - onesCol[j];
diff[i][j] = onesRow + onesCol[j] - zerosRow - zerosCol;
}
}
return diff;
}#include <stdio.h>
#include <stdlib.h>
int** differenceMatrixSinglePass(int** grid, int gridSize, int* gridColSize, int* returnSize, int** returnColumnSizes) {
int m = gridSize;
int n = gridColSize[0];
int** diff = (int**)malloc(m * sizeof(int*));
*returnSize = m;
*returnColumnSizes = (int*)malloc(m * sizeof(int));
for (int i = 0; i < m; i++) {
(*returnColumnSizes)[i] = n;
diff[i] = (int*)malloc(n * sizeof(int));
}
int* onesCol = (int*)calloc(n, sizeof(int));
// Calculate ones in columns simultaneously
for (int j = 0; j < n; j++) {
for (int i = 0; i < m; i++) {
if (grid[i][j] == 1) {
onesCol[j]++;
}
}
}
for (int i = 0; i < m; i++) {
int onesRow = 0, zerosRow = 0;
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
onesRow++;
}
}
zerosRow = n - onesRow;
for (int j = 0; j < n; j++) {
int zerosCol = m - onesCol[j];
diff[i][j] = onesRow + onesCol[j] - zerosRow - zerosCol;
}
}
free(onesCol);
return diff;
}using System;
using System.Linq;
public class Solution {
public int[][] DifferenceMatrixSinglePass(int[][] grid) {
int m = grid.Length;
int n = grid[0].Length;
int[][] diff = new int[m][];
int[] onesCol = new int[n];
// Calculate the number of ones in each column
for (int j = 0; j < n; j++) {
onesCol[j] = grid.Sum(row => row[j]);
}
for (int i = 0; i < m; i++) {
diff[i] = new int[n];
int onesRow = grid[i].Sum();
int zerosRow = n - onesRow;
for (int j = 0; j < n; j++) {
int zerosCol = m - onesCol[j];
diff[i][j] = onesRow + onesCol[j] - zerosRow - zerosCol;
}
}
return diff;
}
}The Python alternative takes advantage of row computations using direct Python techniques like built-in sum functions, reducing the demand for storage while maintaining concise logic, enabling a less storage-heavy approach.
Time Complexity: O(m * n) required for full span calculation.
Space Complexity: O(n) reserved to column counts only, lowering memory usage than the previous method.
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.
function onesMinusZeros(grid: number[][]): number[][] {
const m = grid.length;
const n = grid[0].length;
const rows = new Array(m).fill(0);
const cols = new Array(n).fill(0);
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j]) {
rows[i]++;
cols[j]++;
}
}
}
const ans = Array.from({ length: m }, () => new Array(n).fill(0));
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
ans[i][j] = rows[i] + cols[j] - (m - rows[i]) - (n - cols[j]);
}
}
return ans;
}func onesMinusZeros(grid [][]int) [][]int {
m, n := len(grid), len(grid[0])
rows := make([]int, m)
cols := make([]int, n)
diff := make([][]int, m)
for i, row := range grid {
diff[i] = make([]int, n)
for j, v := range row {
rows[i] += v
cols[j] += v
}
}
for i, r := range rows {
for j, c := range cols {
diff[i][j] = r + c - (n - r) - (m - c)
}
}
return diff
}impl Solution {
pub fn ones_minus_zeros(grid: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
let m = grid.len();
let n = grid[0].len();
let mut rows = vec![0; m];
let mut cols = vec![0; n];
for i in 0..m {
for j in 0..n {
if grid[i][j] == 1 {
rows[i] += 1;
cols[j] += 1;
}
}
}
let mut ans = vec![vec![0; n]; m];
for i in 0..m {
for j in 0..n {
ans[i][j] = (rows[i] + cols[j] - (m - rows[i]) - (n - cols[j])) as i32;
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Precompute Row and Column Counts | Time Complexity: O(m * n) based on iterating through each element of the grid. |
| Optimized Counting in Single Pass | Time Complexity: O(m * n) required for full span calculation. |
| Simulation | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Precompute Row and Column Counts | O(m*n) | O(m+n) | Best general solution. Easy to implement and clearly separates counting and result construction. |
| Optimized Counting with Derived Formula | O(m*n) | O(m+n) | Preferred when simplifying arithmetic and reducing repeated calculations using the derived formula. |
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.