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

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

✓ Brute Force

⏱️ Time: O(m²n²) Space: O(min(m,n))

For every cell in the matrix, we traverse the diagonal from top-left to bottom-right. We count distinct values to the left/above and right/below the current cell separately.

Diagonal Preprocessing

⏱️ Time: O(mn) Space: O(mn)

Instead of recomputing diagonal values for each cell, we preprocess each diagonal once. For each diagonal, we compute prefix and suffix arrays of distinct counts.

Brute Force — Algorithm Steps

Step 1: For each cell (r,c), find the start of its diagonal
Step 2: Traverse diagonal and count distinct values before position (r,c)
Step 3: Traverse diagonal and count distinct values after position (r,c)
Step 4: Calculate absolute difference and store in result

Visualization

Tap to expand

Step-by-Step Walkthrough

Select Cell

For each cell (r,c), find its diagonal

Count Left/Above

Count distinct values before current position

Count Right/Below

Count distinct values after current position

Calculate Difference

Take absolute difference

Code -

solution.c — C

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

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;
    }
    
    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 parseNumber(const char* str, int* pos) {
    int result = 0;
    int sign = 1;
    
    if (str[*pos] == '-') {
        sign = -1;
        (*pos)++;
    }
    
    while (isdigit(str[*pos])) {
        result = result * 10 + (str[*pos] - '0');
        (*pos)++;
    }
    
    return result * sign;
}

int main() {
    char input[10000];
    fgets(input, sizeof(input), stdin);
    
    // Parse the 2D array from JSON format like [[1,2,3],[4,5,6],[7,8,9]]
    int pos = 0;
    while (input[pos] && input[pos] != '[') pos++; // Find first '['
    pos++; // Skip first '['
    
    // Count rows and columns
    int tempPos = pos;
    int rows = 0, cols = 0;
    while (input[tempPos]) {
        if (input[tempPos] == '[') {
            rows++;
            tempPos++;
            int currentCols = 0;
            while (input[tempPos] && input[tempPos] != ']') {
                if (isdigit(input[tempPos]) || input[tempPos] == '-') {
                    currentCols++;
                    while (input[tempPos] && (isdigit(input[tempPos]) || input[tempPos] == '-')) tempPos++;
                } else {
                    tempPos++;
                }
            }
            if (cols == 0) cols = currentCols;
        } else {
            tempPos++;
        }
    }
    
    // Allocate grid
    int** grid = (int**)malloc(rows * sizeof(int*));
    int* gridColSize = (int*)malloc(rows * sizeof(int));
    for (int i = 0; i < rows; i++) {
        grid[i] = (int*)malloc(cols * sizeof(int));
        gridColSize[i] = cols;
    }
    
    // Parse the actual values
    pos = 0;
    while (input[pos] && input[pos] != '[') pos++; // Find first '['
    pos++; // Skip first '['
    
    int row = 0;
    while (input[pos] && row < rows) {
        if (input[pos] == '[') {
            pos++; // Skip '['
            int col = 0;
            while (input[pos] && input[pos] != ']' && col < cols) {
                if (isdigit(input[pos]) || input[pos] == '-') {
                    grid[row][col] = parseNumber(input, &pos);
                    col++;
                } else {
                    pos++;
                }
            }
            row++;
        } else {
            pos++;
        }
    }
    
    int returnSize;
    int* returnColumnSizes;
    
    int** result = solution(grid, rows, gridColSize, &returnSize, &returnColumnSizes);
    
    // Print result in JSON format
    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");
    
    // Free memory
    for (int i = 0; i < rows; i++) {
        free(grid[i]);
        free(result[i]);
    }
    free(grid);
    free(gridColSize);
    free(result);
    free(returnColumnSizes);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²n²)

For each of m×n cells, we potentially traverse the entire diagonal of length up to min(m,n)

⚠ Quadratic Growth

Space Complexity

O(min(m,n))

Hash sets to store distinct values for each diagonal traversal

⚡ 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

Difference of Number of Distinct Values on Diagonals - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler