2711. Difference of Number of Distinct Values on Diagonals
Description
Given a 2D grid
of size m x n
, you should find the matrix answer
of size m x n
.
The cell answer[r][c]
is calculated by looking at the diagonal values of the cell grid[r][c]
:
- Let
leftAbove[r][c]
be the number of distinct values on the diagonal to the left and above the cellgrid[r][c]
not including the cellgrid[r][c]
itself. - Let
rightBelow[r][c]
be the number of distinct values on the diagonal to the right and below the cellgrid[r][c]
, not including the cellgrid[r][c]
itself. - Then
answer[r][c] = |leftAbove[r][c] - rightBelow[r][c]|
.
A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until the end of the matrix is reached.
- For example, in the below diagram the diagonal is highlighted using the cell with indices
(2, 3)
colored gray:- Red-colored cells are left and above the cell.
- Blue-colored cells are right and below the cell.
Return the matrix answer
.
Example 1:
Input: grid = [[1,2,3],[3,1,5],[3,2,1]]
Output: Output: [[1,1,0],[1,0,1],[0,1,1]]
Explanation:
To calculate the answer
cells:
answer | left-above elements | leftAbove | right-below elements | rightBelow | |leftAbove - rightBelow| |
---|---|---|---|---|---|
[0][0] | [] | 0 | [grid[1][1], grid[2][2]] | |{1, 1}| = 1 | 1 |
[0][1] | [] | 0 | [grid[1][2]] | |{5}| = 1 | 1 |
[0][2] | [] | 0 | [] | 0 | 0 |
[1][0] | [] | 0 | [grid[2][1]] | |{2}| = 1 | 1 |
[1][1] | [grid[0][0]] | |{1}| = 1 | [grid[2][2]] | |{1}| = 1 | 0 |
[1][2] | [grid[0][1]] | |{2}| = 1 | [] | 0 | 1 |
[2][0] | [] | 0 | [] | 0 | 0 |
[2][1] | [grid[1][0]] | |{3}| = 1 | [] | 0 | 1 |
[2][2] | [grid[0][0], grid[1][1]] | |{1, 1}| = 1 | [] | 0 | 1 |
Example 2:
Input: grid = [[1]]
Output: Output: [[0]]
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n, grid[i][j] <= 50
Solutions
Solution 1: Simulation
We can simulate the process described in the problem statement, calculating the number of distinct values on the top-left diagonal $tl$ and the bottom-right diagonal $br$ for each cell, then compute their difference $|tl - br|$.
The time complexity is $O(m \times n \times \min(m, n))$, and the space complexity is $O(m \times n)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|