Sponsored
Sponsored
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.
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.
1import java.util.*;
2
3class Solution {
4 public int[][] differenceMatrix(int[][] grid) {
5 int m = grid.length;
6 int n = grid[0].length;
7 int[] onesRow = new int[m];
8 int[] zerosRow = new int[m];
9 int[] onesCol = new int[n];
10 int[] zerosCol = new int[n];
11
12 // Precompute the number of ones and zeros in each row and column
13 for (int i = 0; i < m; i++) {
14 for (int j = 0; j < n; j++) {
15 if (grid[i][j] == 1) {
16 onesRow[i]++;
17 onesCol[j]++;
18 } else {
19 zerosRow[i]++;
20 zerosCol[j]++;
21 }
22 }
23 }
24
25 int[][] diff = new int[m][n];
26 // Create the difference matrix
27 for (int i = 0; i < m; i++) {
28 for (int j = 0; j < n; j++) {
29 diff[i][j] = onesRow[i] + onesCol[j] - zerosRow[i] - zerosCol[j];
30 }
31 }
32 return diff;
33 }
34}
35The Java implementation follows a similar approach as C++ where arrays are used to count ones and zeros. The use of these arrays helps in quickly computing the difference matrix in a straightforward manner once all counts are available.
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.
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).
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;
}
This C++ code follows an optimized path by computing necessary values directly while iterating, resulting in using less additional space for storage other than for column counts.