Difference of Number of Distinct Values on Diagonals — Medium Problem & Solution

Problem statement

You are given an m x n matrix grid. For a cell (r, c) look along its main-direction diagonal (the one running from top-left to bottom-right):

• leftAbove(r, c) is the number of distinct values in the cells (r-1, c-1), (r-2, c-2), … that are inside the grid — strictly above-left of the cell.
• rightBelow(r, c) is the number of distinct values in the cells (r+1, c+1), (r+2, c+2), … — strictly below-right of the cell.

The cell itself is counted in neither. Return an m x n matrix answer with answer[r][c] = |leftAbove(r, c) - rightBelow(r, c)|.

Example 1

Input: grid = [[3,1,2],[4,3,1],[2,4,5]]
Output: [[2,1,0],[1,0,1],[0,1,1]]
Explanation: For `(0,0)` nothing lies above-left and below-right are 3 and 5, so the answer is `|0 - 2| = 2`. For `(2,2)` the above-left cells hold 3 twice — one distinct value — and nothing lies below-right, giving 1.

Example 2

Input: grid = [[7]]
Output: [[0]]

Example 3

Input: grid = [[4,4],[4,9],[2,4]]
Output: [[1,0],[1,1],[0,1]]

Constraints

• m == grid.length
• n == grid[i].length
• 1 <= m, n, grid[i][j] <= 50

How to solve Difference of Number of Distinct Values on Diagonals

Two cells interact only if they lie on the same diagonal, so the matrix splits into m + n - 1 independent sequences; on each, answer = |distinct in the prefix before i − distinct in the suffix after i|.

Approach

1. For each cell (r, c) walk up-left from (r-1, c-1) while inside the grid, marking values in a seen table, and count the distinct ones.
2. Clear the table and do the same walking down-right from (r+1, c+1).
3. Store the absolute difference of the two counts in answer[r][c].

Why it works

The walks visit exactly the cells the definition names, and a value table counts each value once no matter how often it repeats, so each entry is computed straight from its definition. Values are at most 50, so a boolean array of size 51 is a perfect set.

Complexity

• Time — O(m · n · min(m, n))
• Space — O(m · n) for the answer

Pitfalls

• The cell itself belongs to neither side.
• It is the number of distinct values, not the number of cells — repeats count once.
• Only the main-direction diagonal matters; the anti-diagonal is never involved.

Reference solution

Python

from typing import List

def differenceOfDistinctValues(grid: List[List[int]]) -> List[List[int]]:
    m, n = len(grid), len(grid[0])
    ans = [[0] * n for _ in range(m)]
    for r in range(m):
        for c in range(n):
            above = set()
            i, j = r - 1, c - 1
            while i >= 0 and j >= 0:
                above.add(grid[i][j])
                i -= 1
                j -= 1
            below = set()
            i, j = r + 1, c + 1
            while i < m and j < n:
                below.add(grid[i][j])
                i += 1
                j += 1
            ans[r][c] = abs(len(above) - len(below))
    return ans

JavaScript

var differenceOfDistinctValues = function(grid) {
    var m = grid.length, n = grid[0].length;
    var ans = [];
    for (var r = 0; r < m; r++) {
        var row = [];
        for (var c = 0; c < n; c++) {
            var seen = new Array(51).fill(false), a = 0, b = 0;
            for (var i = r - 1, j = c - 1; i >= 0 && j >= 0; i--, j--) {
                if (!seen[grid[i][j]]) { seen[grid[i][j]] = true; a++; }
            }
            seen = new Array(51).fill(false);
            for (var i2 = r + 1, j2 = c + 1; i2 < m && j2 < n; i2++, j2++) {
                if (!seen[grid[i2][j2]]) { seen[grid[i2][j2]] = true; b++; }
            }
            row.push(Math.abs(a - b));
        }
        ans.push(row);
    }
    return ans;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Non-decreasing Subsequences Medium
• Construct the Lexicographically Largest Valid Sequence Medium
• Matchsticks to Square Medium
• Combination Sum III Medium
• Combination Sum II Medium
• Permutations II Medium