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

Python3JavaC++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

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;
    }
}

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;
    }
};

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
}

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;
}

Comments