Skip to content

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

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
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
 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
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;
    }
}
 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
class Solution {
public:
    vector<vector<int>> differenceOfDistinctValues(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();