We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Difference of Number of Distinct Values on Diagonals

Difficulty: Medium

Problem Description

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]|.

Return the matrix answer.

Key Insights

  • The problem requires calculating distinct values in two diagonals for each cell in the grid.
  • The left-above diagonal consists of elements that can be accessed by moving up and left from the current position.
  • The right-below diagonal consists of elements that can be accessed by moving down and right from the current position.
  • Using sets can help efficiently count distinct values in the diagonals.

Space and Time Complexity

Time Complexity: O(m * n * min(m, n)), where m is the number of rows and n is the number of columns. Each cell needs to traverse its respective diagonals to count distinct values.

Space Complexity: O(min(m, n)) for storing the distinct values in sets for the diagonals.

Solution

To solve the problem, we can use two nested loops to iterate through each cell in the grid. For each cell, we will:

  1. Initialize two sets to store distinct values for the left-above and right-below diagonals.
  2. Use a loop to traverse the left-above diagonal from the current cell to the top-left corner, adding values to the left-above set.
  3. Use another loop to traverse the right-below diagonal from the current cell to the bottom-right corner, adding values to the right-below set.
  4. Calculate the absolute difference between the sizes of the two sets and store it in the answer matrix.

Code Solutions

def difference_of_distinct_values(grid):
    m, n = len(grid), len(grid[0])
    answer = [[0] * n for _ in range(m)]
    
    for r in range(m):
        for c in range(n):
            leftAbove = set()
            rightBelow = set()
            
            # Collect left-above diagonal values
            x, y = r - 1, c - 1
            while x >= 0 and y >= 0:
                leftAbove.add(grid[x][y])
                x -= 1
                y -= 1
            
            # Collect right-below diagonal values
            x, y = r + 1, c + 1
            while x < m and y < n:
                rightBelow.add(grid[x][y])
                x += 1
                y += 1
            
            # Calculate answer[r][c]
            answer[r][c] = abs(len(leftAbove) - len(rightBelow))
    
    return answer
← Back to All Questions