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:
ith row be onesRowi.jth column be onesColj.ith row be zerosRowi.jth column be zerosColj.diff[i][j] = onesRowi + onesColj - zerosRowi - zerosColjReturn 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 either 0 or 1.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.
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.
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.
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.
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).
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.
| Approach | Complexity |
|---|---|
| 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. |
| Optimized Counting in Single Pass | Time Complexity: O(m * n) because every element is iterated over during the counting and result generation stages. |
| Simulation | — |
| 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. |
Difference Between Ones and Zeros in Row and Column | Intuition | Leetcode-2482 • codestorywithMIK • 3,678 views views
Watch 9 more video solutions →Practice Difference Between Ones and Zeros in Row and Column with our built-in code editor and test cases.
Practice on FleetCode