Skip to content

2711. Difference of Number of Distinct Values on Diagonals 👎

  • Time: $O(mn)$
  • Space: $O(mn)$
 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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--]);
    }
  }
};

 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
27
28
29
30
31
32
33
34
35
36
37
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--]);
    }
  }
}

 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
27
28
29
30
31
32
33
34
35
36
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