LeetCode 2711. Difference of Number of Distinct Values on Diagonals Solution in Java, C++, Python & More | Explanation + Code

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:

  <ul>
  	<li>Red-colored cells are left and above the cell.</li>
  	<li>Blue-colored cells are right and below the cell.</li>
  </ul>
  </li>
  

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 × n × min(m, n)), and the space complexity is O(m × n).

PythonJavaC++GoTypeScript

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(code-box)

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; } }(code-box)

class Solution { public: vector<vector<int>> differenceOfDistinctValues(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); vector<vector<int>> ans(m, vector<int>(n)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { int x = i, y = j; unordered_set<int> 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; } };(code-box)

func differenceOfDistinctValues(grid [][]int) [][]int { m, n := len(grid), len(grid[0]) ans := make([][]int, m) for i := range grid { ans[i] = make([]int, n) for j := range grid[i] { x, y := i, j s := map[int]bool{} for x > 0 && y > 0 { x, y = x-1, y-1 s[grid[x][y]] = true } tl := len(s) x, y = i, j s = map[int]bool{} for x+1 < m && y+1 < n { x, y = x+1, y+1 s[grid[x][y]] = true } br := len(s) ans[i][j] = abs(tl - br) } } return ans } func abs(x int) int { if x < 0 { return -x } return x }(code-box)

function differenceOfDistinctValues(grid: number[][]): number[][] { const m = grid.length; const n = grid[0].length; const ans: number[][] = Array(m) .fill(0) .map(() => Array(n).fill(0)); for (let i = 0; i < m; ++i) { for (let j = 0; j < n; ++j) { let [x, y] = [i, j]; const s = new Set<number>(); while (x && y) { s.add(grid[--x][--y]); } const tl = s.size; [x, y] = [i, j]; s.clear(); while (x + 1 < m && y + 1 < n) { s.add(grid[++x][++y]); } const br = s.size; ans[i][j] = Math.abs(tl - br); } } return ans; }(code-box)