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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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).
| 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. |
✅ Difference Between Ones and Zeros in Row and Column - Elegant - 2D Arrays - Matrix - LeetCode 2482 • Leet Logics • 951 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