Difference of Number of Distinct Values on Diagonals

Difference of Number of Distinct Values on Diagonals - Problem

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.

Return the matrix answer.

Input & Output

Example 1 — Basic 3x3 Grid

$ Input: grid = [[1,2,3],[4,5,6],[7,8,9]]

› Output: [[2,1,0],[1,0,1],[0,1,2]]

💡 Note: For cell (1,1) with value 5: left/above has {1} (1 distinct), right/below has {9} (1 distinct), so |1-1|=0. For cell (0,0): no left/above (0 distinct), right/below has {5,9} (2 distinct), so |0-2|=2.

Example 2 — Small 2x2 Grid

$ Input: grid = [[1,2],[3,4]]

› Output: [[1,0],[0,1]]

💡 Note: Cell (0,0): no left/above, right/below has {4}, difference=1. Cell (1,1): left/above has {1}, no right/below, difference=1.

Example 3 — Duplicate Values

$ Input: grid = [[1,1,1],[1,1,1],[1,1,1]]

› Output: [[0,0,0],[0,0,0],[0,0,0]]

💡 Note: All values are the same, so each diagonal has at most 1 distinct value. Every cell will have equal counts on both sides, resulting in difference 0.

Constraints

1 ≤ m, n ≤ 50
1 ≤ grid[i][j] ≤ 50

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

3x3 grid with values 1-9

Diagonal Analysis

Count distinct values left/above vs right/below each cell

Result Matrix

Absolute differences for each position

Key Takeaway

🎯 Key Insight: Each diagonal can be processed independently to count distinct values efficiently

Asked in

G Google 25 M Microsoft 18 a Amazon 15 f Facebook 12

The key insight is that each cell belongs to exactly one diagonal, and we need to count distinct values before and after each cell's position on that diagonal. The optimal approach preprocesses each diagonal to compute prefix and suffix distinct counts, avoiding redundant work. Time: O(mn), Space: O(mn).

Common Approaches

Approach	Time	Space	Notes
✓ Diagonal Preprocessing	O(mn)	O(mn)	Precompute distinct counts for each diagonal to avoid repeated work
Brute Force	O(m²n²)	O(min(m,n))	For each cell, traverse the diagonal twice to count distinct values

Diagonal Preprocessing — Algorithm Steps

Step 1: Identify all diagonals in the matrix
Step 2: For each diagonal, build prefix array of distinct counts
Step 3: For each diagonal, build suffix array of distinct counts
Step 4: For each cell, lookup precomputed values and calculate difference

Visualization

Tap to expand

Step-by-Step Walkthrough

Group by Diagonal

Identify cells belonging to same diagonal

Prefix Counts

Count distinct values from start to each position

Suffix Counts

Count distinct values from each position to end

Lookup Results

Use precomputed values for O(1) lookup

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int r, c, val;
} Cell;

int compare(const void* a, const void* b) {
    Cell* ca = (Cell*)a;
    Cell* cb = (Cell*)b;
    return ca->r - cb->r;
}

int** solution(int** grid, int gridSize, int* gridColSize, int* returnSize, int** returnColumnSizes) {
    int m = gridSize, n = gridColSize[0];
    int** answer = (int**)malloc(m * sizeof(int*));
    *returnSize = m;
    *returnColumnSizes = (int*)malloc(m * sizeof(int));
    
    for (int i = 0; i < m; i++) {
        answer[i] = (int*)malloc(n * sizeof(int));
        (*returnColumnSizes)[i] = n;
    }
    
    // Simple approach for C implementation
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            // Find diagonal start
            int startR = r, startC = c;
            while (startR > 0 && startC > 0) {
                startR--;
                startC--;
            }
            
            // Count distinct values left/above
            int leftValues[1000];
            int leftCount = 0;
            int currR = startR, currC = startC;
            while (currR < m && currC < n) {
                if (currR == r && currC == c) break;
                
                int found = 0;
                for (int i = 0; i < leftCount; i++) {
                    if (leftValues[i] == grid[currR][currC]) {
                        found = 1;
                        break;
                    }
                }
                if (!found) {
                    leftValues[leftCount++] = grid[currR][currC];
                }
                
                currR++;
                currC++;
            }
            
            // Count distinct values right/below
            int rightValues[1000];
            int rightCount = 0;
            currR = r + 1;
            currC = c + 1;
            while (currR < m && currC < n) {
                int found = 0;
                for (int i = 0; i < rightCount; i++) {
                    if (rightValues[i] == grid[currR][currC]) {
                        found = 1;
                        break;
                    }
                }
                if (!found) {
                    rightValues[rightCount++] = grid[currR][currC];
                }
                
                currR++;
                currC++;
            }
            
            int diff = leftCount - rightCount;
            answer[r][c] = diff < 0 ? -diff : diff;
        }
    }
    
    return answer;
}

int main() {
    // Simple test case parsing for demonstration
    int grid[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
    int* gridRows[3] = {grid[0], grid[1], grid[2]};
    int gridColSize[3] = {3, 3, 3};
    int returnSize;
    int* returnColumnSizes;
    
    int** result = solution(gridRows, 3, gridColSize, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("[");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            if (j > 0) printf(",");
            printf("%d", result[i][j]);
        }
        printf("]");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(mn)

Each cell is visited constant times: once during preprocessing and once during result calculation

✓ Linear Growth

Space Complexity

O(mn)

Additional arrays to store prefix/suffix distinct counts for each diagonal

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

842 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Diagonal Preprocessing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler