Difference of Number of Distinct Values on Diagonals
MedPrompt
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.lengthn == grid[i].length1 <= m, n, grid[i][j] <= 50
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. For each cell (r, c) in the grid, it independently calculates the number of distinct values in the top-left diagonal and the bottom-right diagonal.
Algorithm
- Initialize an
m x nmatrixanswer. - For each row
rfrom0tom-1: - For each column
cfrom0ton-1: -
// Calculate leftAbove[r][c] -
Create a `HashSet` `topLeftSet`. -
Iterate with `i = r-1`, `j = c-1` as long as `i >= 0` and `j >= 0`: -
Add `grid[i][j]` to `topLeftSet`. -
Decrement `i` and `j`. -
`leftAbove = topLeftSet.size()`. - // Calculate rightBelow[r][c]
- Create a
HashSetbottomRightSet. - Iterate with
i = r+1,j = c+1as long asi < mandj < n: -
Add `grid[i][j]` to `bottomRightSet`. -
Increment `i` and `j`. rightBelow = bottomRightSet.size().- // Store the result
answer[r][c] = Math.abs(leftAbove - rightBelow).- Return
answer.
Walkthrough
We iterate through every cell (r, c) of the grid. For each cell, we perform two separate traversals:
- Top-Left Diagonal (
leftAbove): We traverse from(r-1, c-1)up towards the grid boundaries. We use aHashSetto collect all the values encountered, and its size gives us the count of distinct elements. - Bottom-Right Diagonal (
rightBelow): We traverse from(r+1, c+1)down towards the grid boundaries. Similarly, we use anotherHashSetto find the count of distinct elements.
The value for answer[r][c] is then the absolute difference between these two counts. This process is repeated for all m * n cells.
import java.util.HashSet;import java.util.Set; class Solution { public int[][] differenceOfDistinctValues(int[][] grid) { int m = grid.length; int n = grid[0].length; int[][] answer = new int[m][n]; for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { // Calculate leftAbove Set<Integer> topLeftSet = new HashSet<>(); int i = r - 1; int j = c - 1; while (i >= 0 && j >= 0) { topLeftSet.add(grid[i][j]); i--; j--; } int leftAbove = topLeftSet.size(); // Calculate rightBelow Set<Integer> bottomRightSet = new HashSet<>(); i = r + 1; j = c + 1; while (i < m && j < n) { bottomRightSet.add(grid[i][j]); i++; j++; } int rightBelow = bottomRightSet.size(); answer[r][c] = Math.abs(leftAbove - rightBelow); } } return answer; }}Complexity
Time
O(m * n * min(m, n)). For each of the `m * n` cells, we traverse its top-left and bottom-right diagonals. The maximum length of a diagonal is `min(m, n)`, leading to this complexity.
Space
O(min(m, n)). For each cell, we create two `HashSet`s. The maximum size of a set is bounded by the length of the diagonal, which is `min(m, n)`. This is the auxiliary space, excluding the `O(m * n)` space for the output matrix.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the problem definition.
Cons
Inefficient due to redundant calculations. The distinct counts for overlapping diagonal segments are re-calculated multiple times for different cells.
Solutions
Solution
class Solution {public int[][] differenceOfDistinctValues(int[][] grid) { int m = grid.length, n = grid[0].length; int[][] ans = new int[m][n]; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { int x = i, y = j; Set<Integer> s = new HashSet<>(); while (x > 0 && y > 0) { s.add(grid[--x][--y]); } int tl = s.size(); x = i; y = j; s.clear(); while (x < m - 1 && y < n - 1) { s.add(grid[++x][++y]); } int br = s.size(); ans[i][j] = Math.abs(tl - br); } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.