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.
1function differenceMatrix(grid) {
2 const m = grid.length;
3 const n = grid[0].length;
4 const onesRow = new Array(m).fill(0);
5 const zerosRow = new Array(m).fill(0);
6 const onesCol = new Array(n).fill(0);
7 const zerosCol = new Array(n).fill(0);
8
9 // Precompute the number of ones and zeros in each row and column
10 for (let i = 0; i < m; i++) {
11 for (let j = 0; j < n; j++) {
12 if (grid[i][j] === 1) {
13 onesRow[i]++;
14 onesCol[j]++;
15 } else {
16 zerosRow[i]++;
17 zerosCol[j]++;
18 }
19 }
20 }
21
22 const diff = Array.from({ length: m }, () => new Array(n).fill(0));
23 // Create the difference matrix
24 for (let i = 0; i < m; i++) {
25 for (let j = 0; j < n; j++) {
26 diff[i][j] = onesRow[i] + onesCol[j] - zerosRow[i] - zerosCol[j];
27 }
28 }
29 return diff;
30}
31The JavaScript solution utilises arrays to store the precomputed values of ones and zeros for each row and column. This allows for a simple summation and subtraction to determine the difference matrix as required.
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).
This Java solution computes necessary counts dynamically during the matrix traversal. By exploiting single-row computations and reduced storage for columns, it achieves optimal performance without sacrificing clarity.