Difference of Number of Distinct Values on Diagonals

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.

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.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int[][] differenceOfDistinctValues(int[][] grid) {6        int m = grid.length;7        int n = grid[0].length;8        int[][] answer = new int[m][n];9 10        for (int r = 0; r < m; r++) {11            for (int c = 0; c < n; c++) {12                // Calculate leftAbove13                Set<Integer> topLeftSet = new HashSet<>();14                int i = r - 1;15                int j = c - 1;16                while (i >= 0 && j >= 0) {17                    topLeftSet.add(grid[i][j]);18                    i--;19                    j--;20                }21                int leftAbove = topLeftSet.size();22 23                // Calculate rightBelow24                Set<Integer> bottomRightSet = new HashSet<>();25                i = r + 1;26                j = c + 1;27                while (i < m && j < n) {28                    bottomRightSet.add(grid[i][j]);29                    i++;30                    j++;31                }32                int rightBelow = bottomRightSet.size();33 34                answer[r][c] = Math.abs(leftAbove - rightBelow);35            }36        }37        return answer;38    }39}

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.

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).

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int[][] differenceOfDistinctValues(int[][] grid) {6        int m = grid.length;7        int n = grid[0].length;8        int[][] answer = new int[m][n];9 10        // Process diagonals starting from the top row11        for (int j = 0; j < n; j++) {12            processDiagonal(grid, answer, 0, j, m, n);13        }14 15        // Process diagonals starting from the left column (skip (0,0) as it's covered)16        for (int i = 1; i < m; i++) {17            processDiagonal(grid, answer, i, 0, m, n);18        }19 20        return answer;21    }22 23    private void processDiagonal(int[][] grid, int[][] answer, int startR, int startC, int m, int n) {24        // Forward pass for leftAbove25        Set<Integer> distinctElements = new HashSet<>();26        int r = startR;27        int c = startC;28        while (r < m && c < n) {29            answer[r][c] = distinctElements.size();30            distinctElements.add(grid[r][c]);31            r++;32            c++;33        }34 35        // Backward pass for rightBelow36        distinctElements.clear();37        r--; // Start from the last element of the diagonal38        c--;39        while (r >= startR && c >= startC) {40            int rightBelowCount = distinctElements.size();41            answer[r][c] = Math.abs(answer[r][c] - rightBelowCount);42            distinctElements.add(grid[r][c]);43            r--;44            c--;45        }46    }47}