LeetCode Solutions Blog

Difference of Number of Distinct Values on Diagonals

Number: 2801

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an m x n grid, for each cell compute two values:

leftAbove[r][c]: the number of distinct elements on the top-left diagonal from (r, c), excluding grid[r][c].
rightBelow[r][c]: the number of distinct elements on the bottom-right diagonal from (r, c), excluding grid[r][c]. Then, answer[r][c] = |leftAbove[r][c] − rightBelow[r][c]|. Return the answer matrix.

Key Insights

All cells that lie on the same diagonal share the same r - c constant. This lets us process diagonals independently.
For each diagonal, compute prefix distinct counts (for left-above values) and suffix distinct counts (for right-below values).
Using precomputation per diagonal avoids recomputing sets repeatedly for every cell.

Space and Time Complexity

Time Complexity: O(mn) – each cell is processed as part of its diagonal. Space Complexity: O(mn) – additional space is used for storing distinct counts for each diagonal.

Solution

The approach is to group cells by their diagonal using the key (r - c). For each diagonal, we get cells in order from top-left to bottom-right. We then build two arrays:

Prefix array: For each cell at index i on the diagonal, store the count of distinct values from the start until i-1.
Suffix array: For each cell at index i, store the count of distinct values from i+1 until the end. Finally, for each cell we compute the absolute difference between its prefix and suffix distinct counts and assign that value to answer[r][c]. This method efficiently calculates the required value using set and dictionary operations to track distinct elements.

Code Solutions

# Python solution for the problem

def differenceOfDistinctValues(grid):
    m, n = len(grid), len(grid[0])
    # initialize answer matrix with zeros
    answer = [[0] * n for _ in range(m)]
    
    # dictionary to collect diagonal cells: key = r - c, value = list of (r, c)
    diagonals = {}
    for r in range(m):
        for c in range(n):
            key = r - c
            if key not in diagonals:
                diagonals[key] = []
            diagonals[key].append((r, c))
    
    # Process each diagonal separately
    for diag in diagonals.values():
        size = len(diag)
        prefix = [0] * size  # distinct count of elements before current cell in this diagonal
        suffix = [0] * size  # distinct count of elements after current cell in this diagonal
        
        # Compute prefix distinct counts
        seen = set()
        for i in range(size):
            # prefix count for cell i is number of distinct elements seen so far
            prefix[i] = len(seen)
            r, c = diag[i]
            seen.add(grid[r][c])
            
        # Compute suffix distinct counts
        seen = set()
        for i in range(size - 1, -1, -1):
            r, c = diag[i]
            suffix[i] = len(seen)
            seen.add(grid[r][c])
        
        # Fill the result for cells in the diagonal using prefix and suffix arrays
        for i in range(size):
            r, c = diag[i]
            # cell answer is the absolute difference between prefix and suffix counts
            answer[r][c] = abs(prefix[i] - suffix[i])
    
    return answer

# Example usage:
grid = [[1,2,3],[3,1,5],[3,2,1]]
print(differenceOfDistinctValues(grid))  # Expected output: [[1,1,0],[1,0,1],[0,1,1]]