2711. Difference of Number of Distinct Values on Diagonals LeetCode Solution
In this guide, you will get 2711. Difference of Number of Distinct Values on Diagonals LeetCode Solution with the best time and space complexity. The solution to Difference of Number of Distinct Values on Diagonals problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Difference of Number of Distinct Values on Diagonals solution in C++
- Difference of Number of Distinct Values on Diagonals solution in Java
- Difference of Number of Distinct Values on Diagonals solution in Python
- Additional Resources
Problem Statement of Difference of Number of Distinct Values on Diagonals
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
Complexity Analysis
- Time Complexity: O(mn)
- Space Complexity: O(mn)
2711. Difference of Number of Distinct Values on Diagonals LeetCode Solution in C++
class Solution {
public:
vector<vector<int>> differenceOfDistinctValues(vector<vector<int>>& grid) {
const int m = grid.size();
const int n = grid[0].size();
vector<vector<int>> ans(m, vector<int>(n));
for (int i = 0; i < m; ++i)
fillInDiagonal(grid, i, 0, ans);
for (int j = 1; j < n; ++j)
fillInDiagonal(grid, 0, j, ans);
return ans;
}
private:
void fillInDiagonal(const vector<vector<int>>& grid, int i, int j,
vector<vector<int>>& ans) {
unordered_set<int> topLeft;
unordered_set<int> bottomRight;
// Fill in the diagonal from the top-left to the bottom-right.
while (i < grid.size() && j < grid[0].size()) {
ans[i][j] = topLeft.size();
// Post-addition, so this information can be utilized in subsequent cells.
topLeft.insert(grid[i++][j++]);
}
--i;
--j;
// Fill in the diagonal from the bottom-right to the top-left.
while (i >= 0 && j >= 0) {
ans[i][j] = abs(ans[i][j] - static_cast<int>(bottomRight.size()));
// Post-addition, so this information can be utilized in subsequent cells.
bottomRight.insert(grid[i--][j--]);
}
}
};
/* code provided by PROGIEZ */2711. Difference of Number of Distinct Values on Diagonals LeetCode Solution in Java
class Solution {
public int[][] differenceOfDistinctValues(int[][] grid) {
final int m = grid.length;
final int n = grid[0].length;
int[][] ans = new int[m][n];
for (int i = 0; i < m; ++i)
fillInDiagonal(grid, i, 0, ans);
for (int j = 1; j < n; ++j)
fillInDiagonal(grid, 0, j, ans);
return ans;
}
private void fillInDiagonal(int[][] grid, int i, int j, int[][] ans) {
Set<Integer> topLeft = new HashSet<>();
Set<Integer> bottomRight = new HashSet<>();
// Fill in the diagonal from the top-left to the bottom-right.
while (i < grid.length && j < grid[0].length) {
ans[i][j] = topLeft.size();
// Post-addition, so this information can be utilized in subsequent cells.
topLeft.add(grid[i++][j++]);
}
--i;
--j;
// Fill in the diagonal from the bottom-right to the top-left.
while (i >= 0 && j >= 0) {
ans[i][j] = Math.abs(ans[i][j] - bottomRight.size());
// Post-addition, so this information can be utilized in subsequent cells.
bottomRight.add(grid[i--][j--]);
}
}
}
// code provided by PROGIEZ2711. Difference of Number of Distinct Values on Diagonals LeetCode Solution in Python
class Solution:
def differenceOfDistinctValues(self, grid: list[list[int]]) -> list[list[int]]:
m = len(grid)
n = len(grid[0])
ans = [[0] * n for _ in range(m)]
def fillInDiagonal(i: int, j: int) -> None:
topLeft = set()
bottomRight = set()
# Fill in the diagonal from the top-left to the bottom-right.
while i < len(grid) and j < len(grid[0]):
ans[i][j] = len(topLeft)
# Post-addition, so this information can be utilized in subsequent cells.
topLeft.add(grid[i][j])
i += 1
j += 1
i -= 1
j -= 1
# Fill in the diagonal from the bottom-right to the top-left.
while i >= 0 and j >= 0:
ans[i][j] = abs(ans[i][j] - len(bottomRight))
# Post-addition, so this information can be utilized in subsequent cells.
bottomRight.add(grid[i][j])
i -= 1
j -= 1
for i in range(m):
fillInDiagonal(i, 0)
for j in range(1, n):
fillInDiagonal(0, j)
return ans
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.