# Difference of Number of Distinct Values on Diagonals **Difficulty:** MEDIUM [External](https://leetcode.com/problems/difference-of-number-of-distinct-values-on-diagonals) Canonical: https://scaleengineer.com/dsa/problems/difference-of-number-of-distinct-values-on-diagonals **Data structures:** Array, Hash Table, Matrix --- ## Problem 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 cell `grid[r][c]` not including the cell `grid[r][c]` itself. * Let `rightBelow[r][c]` be the number of **distinct** values on the diagonal to the right and below the cell `grid[r][c]`, not including the cell `grid[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. ![](https://assets.glich.co/dsa/difference-of-number-of-distinct-values-on-diagonals/image0.png) 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` # Approaches ## Brute-Force Simulation 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. **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. **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. ### Explanation We iterate through every cell `(r, c)` of the `grid`. For each cell, we perform two separate traversals: 1. **Top-Left Diagonal (`leftAbove`):** We traverse from `(r-1, c-1)` up towards the grid boundaries. We use a `HashSet` to collect all the values encountered, and its size gives us the count of distinct elements. 2. **Bottom-Right Diagonal (`rightBelow`):** We traverse from `(r+1, c+1)` down towards the grid boundaries. Similarly, we use another `HashSet` to 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. ```java 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 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 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; } } ``` ### Algorithm 1. Initialize an `m x n` matrix `answer`. 2. For each row `r` from `0` to `m-1`: 3. For each column `c` from `0` to `n-1`: 4. // Calculate leftAbove[r][c] 5. Create a `HashSet` `topLeftSet`. 6. Iterate with `i = r-1`, `j = c-1` as long as `i >= 0` and `j >= 0`: 7. Add `grid[i][j]` to `topLeftSet`. 8. Decrement `i` and `j`. 9. `leftAbove = topLeftSet.size()`. 10. // Calculate rightBelow[r][c] 11. Create a `HashSet` `bottomRightSet`. 12. Iterate with `i = r+1`, `j = c+1` as long as `i < m` and `j < n`: 13. Add `grid[i][j]` to `bottomRightSet`. 14. Increment `i` and `j`. 15. `rightBelow = bottomRightSet.size()`. 16. // Store the result 17. `answer[r][c] = Math.abs(leftAbove - rightBelow)`. 18. Return `answer`. ## Optimized Diagonal-wise Processing This approach improves upon the brute-force method by processing the grid one diagonal at a time. By traversing each diagonal twice (once forward and once backward), we can efficiently calculate `leftAbove` and `rightBelow` for all cells on that diagonal without redundant computations. **Time:** O(m * n). Each cell in the grid is visited exactly twice: once during a forward pass and once during a backward pass on its diagonal. The operations inside the loops (set insertion and size check) take constant time on average. · **Space:** O(min(m, n)). The auxiliary space required is for the `HashSet`, which at most stores all elements on the longest diagonal. The length of the longest diagonal is `min(m, n)`. Given the constraints on grid values, a frequency array of size 51 could be used, making the auxiliary space `O(1)` (constant). The `O(m*n)` space for the output matrix is not counted as auxiliary. **Pros:** Highly efficient, with optimal time complexity.; Avoids redundant computations by processing each diagonal cohesively. **Cons:** The logic is slightly more complex than the brute-force approach, involving separate handling of diagonals and two passes. ### Explanation The key observation is that for any two cells on the same diagonal, their `leftAbove` and `rightBelow` sets are related. For a cell `(r, c)`, the set of distinct elements for `leftAbove` of `(r+1, c+1)` is simply the set for `leftAbove` of `(r, c)` with the element `grid[r][c]` added. We can iterate through all `m + n - 1` diagonals. Diagonals are identified by their starting cell, which is either in the first row `(0, j)` or the first column `(i, 0)`. For each diagonal: 1. **Forward Pass (for `leftAbove`):** We traverse the diagonal from top-left to bottom-right. We maintain a set of unique elements seen so far. For each cell `(r, c)`, the size of this set gives `leftAbove[r][c]`. We store this value temporarily in our `answer` matrix. After processing the cell, we add `grid[r][c]` to the set. 2. **Backward Pass (for `rightBelow`):** We traverse the same diagonal from bottom-right to top-left. We again maintain a set of unique elements. For each cell `(r, c)`, the size of this set gives `rightBelow[r][c]`. We then calculate the final answer for this cell: `answer[r][c] = |answer[r][c] - rightBelow[r][c]|`. After processing, we add `grid[r][c]` to the set for the next iteration (the cell to its top-left). Since the values in the grid are small (1-50), we can use a frequency array of size 51 instead of a `HashSet` for a slight performance gain, making set operations true O(1). ```java 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]; // Process diagonals starting from the top row for (int j = 0; j < n; j++) { processDiagonal(grid, answer, 0, j, m, n); } // Process diagonals starting from the left column (skip (0,0) as it's covered) for (int i = 1; i < m; i++) { processDiagonal(grid, answer, i, 0, m, n); } return answer; } private void processDiagonal(int[][] grid, int[][] answer, int startR, int startC, int m, int n) { // Forward pass for leftAbove Set distinctElements = new HashSet<>(); int r = startR; int c = startC; while (r < m && c < n) { answer[r][c] = distinctElements.size(); distinctElements.add(grid[r][c]); r++; c++; } // Backward pass for rightBelow distinctElements.clear(); r--; // Start from the last element of the diagonal c--; while (r >= startR && c >= startC) { int rightBelowCount = distinctElements.size(); answer[r][c] = Math.abs(answer[r][c] - rightBelowCount); distinctElements.add(grid[r][c]); r--; c--; } } } ``` ### Algorithm 1. Initialize an `m x n` matrix `answer`. 2. // Process diagonals starting from the top row 3. For each column `j` from `0` to `n-1`: 4. // Forward pass for leftAbove 5. Create a set `distinct_elements`. 6. Iterate along the diagonal starting at `(0, j)`: for `r, c = 0, j`, `1, j+1`, ... 7. `answer[r][c] = distinct_elements.size()`. 8. Add `grid[r][c]` to `distinct_elements`. 9. // Backward pass for rightBelow 10. Clear `distinct_elements`. 11. Iterate backwards along the same diagonal: 12. `rightBelowCount = distinct_elements.size()`. 13. `answer[r][c] = Math.abs(answer[r][c] - rightBelowCount)`. 14. Add `grid[r][c]` to `distinct_elements`. 15. // Process diagonals starting from the left column (excluding the one at (0,0) already processed) 16. For each row `i` from `1` to `m-1`: 17. // Repeat steps 4-14 for the diagonal starting at `(i, 0)`. 18. Return `answer`. # Solutions ### Java ```java 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 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; } } ``` ### CPP ```cpp class Solution { public: vector> differenceOfDistinctValues(vector> &grid) { int m = grid.size(), n = grid[0].size(); vector> ans(m, vector(n)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { int x = i, y = j; unordered_set s; while (x > 0 && y > 0) { s.insert(grid[--x][--y]); } int tl = s.size(); x = i; y = j; s.clear(); while (x < m - 1 && y < n - 1) { s.insert(grid[++x][++y]); } int br = s.size(); ans[i][j] = abs(tl - br); } } return ans; } }; ``` ### Python ```python class Solution: def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]: m, n = len(grid), len(grid[0]) ans = [[0] * n for _ in range(m)] for i in range(m): for j in range(n): x, y = i, j s = set() while x and y: x, y = x - 1, y - 1 s . add(grid[x][y]) tl = len(s) x, y = i, j s = set() while x + 1 < m and y + 1 < n: x, y = x + 1, y + 1 s . add(grid[x][y]) br = len(s) ans[i][j] = abs(tl - br) return ans ```