2711. Difference of Number of Distinct Values on Diagonals
Problem Description
The task is to compute a matrix answer
based on another 2D grid
given as input. The grid
is a two-dimensional array with m
rows and n
columns, and we want to create a new 2D array answer
of the same dimensions.
For each cell in the answer
matrix at position (r, c)
, the value is determined as follows:
-
topLeft[r][c]
: count the number of distinct values that appear in the cells on the top-left diagonal of cell(r, c)
in the originalgrid
. This diagonal includes cells(x, y)
from the top row or the leftmost column cutting through to just above(r, c)
such thatx < r and y < c
. -
bottomRight[r][c]
: count the number of distinct values that appear in the cells on the bottom-right diagonal of cell(r, c)
in the originalgrid
. This diagonal includes cells(x, y)
starting just below(r, c)
running down to the bottom right corner of the grid such thatx > r and y > c
.
The value in answer[r][c]
is the absolute difference between these two counts: |topLeft[r][c] - bottomRight[r][c]|
.
The problem requires returning the matrix answer
, which is constructed by performing these computations for every cell (r, c)
of grid
.
Intuition
The intuition behind the solution is to focus on each cell (r, c)
individually and to accumulate the distinct values along its top-left and bottom-right diagonals. Using sets is helpful because sets naturally maintain unique elements, thereby making the counting of distinct values straightforward.
For the top-left diagonal, we start from the current cell (r, c)
and move upwards and to the left (x - 1, y - 1)
until we either reach the first row or the first column.
For the bottom-right diagonal, we start from the current cell (r, c)
and move downwards and to the right (x + 1, y + 1)
until we either reach the last row or the last column.
At each step for both diagonals, we add the values of grid[x][y]
to their respective sets. Once all unique values are accumulated, the sizes of the sets represent the count of distinct values in each diagonal. We calculate the absolute difference of these counts and assign it to answer[r][c]
.
This process is repeated for every cell in the grid
, which eventually yields the completed answer
matrix. The brute force nature of this solution is acceptable given the problem constraints, and it directly translates the problem's requirements into algorithmic steps to find the solution.
Solution Approach
The solution as implemented above employs a straightforward, brute-force approach. To compute the answer[r][c]
, the algorithm inspects two distinct diagonals for each cell (r, c)
in the grid
. Here is a step-by-step breakdown of the approach:
-
Initialize a matrix
ans
with the same dimensions asgrid
but filled with zeros. This will store the final results. -
Traverse every cell
(r, c)
in the grid. Use nested loops, the outer loop running through the rows, and the inner loop going through the columns. -
To find
topLeft[r][c]
, initialize an empty sets
. Then, iterate from the current cell upwards and leftward diagonally (decreasing both row and column indices). For each cell encountered, add the value of the cell fromgrid[x][y]
to the sets
. The loop stops when reaching the top row or the leftmost column. After iteration,tl
is set as the length of the sets
, which is the count of unique values in the top-left diagonal.x, y = i, j s = set() while x and y: x, y = x - 1, y - 1 s.add(grid[x][y]) tl = len(s)
-
Repeat a similar process to find
bottomRight[r][c]
. Initialize another empty sets
, and iterate from the current cell downwards and rightward diagonally (increasing both row and column indices). Add the value fromgrid[x][y]
to sets
until reaching the bottom row or the rightmost column. Assignbr
as the length of this set.x, y = i, j s = set() while x + 1 < m and y + 1 < n: x, y = x + 1, y + 1 s.add(grid[x][y]) br = len(s)
-
Calculate the absolute difference between
tl
andbr
and assign it toans[i][j]
. This step executes for every cell(r, c)
, filling theans
matrix.ans[i][j] = abs(tl - br)
-
After filling in all values, return the
ans
matrix.
Using this method, every cell in the grid
is visited, and its corresponding diagonals are processed to determine the values of answer[r][c]
. The utilization of sets for counting unique elements is pivotal because it eliminates the need for manual checks for duplicates, simplifying the code and ensuring accuracy.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through a small example to illustrate the solution approach.
Suppose we have the following grid
matrix:
grid = [ [1, 2, 3], [4, 1, 6], [7, 8, 1] ]
We want to construct an answer
matrix where each element is the absolute difference between the count of distinct numbers in its top-left and bottom-right diagonals.
Step-by-step Process:
- Initialize an
answer
matrix with zeros having the same dimensions asgrid
:
answer = [ [0, 0, 0], [0, 0, 0], [0, 0, 0] ]
- Start iterating over each cell
(r, c)
of the grid. First with cell(0, 0)
:- There is no top-left diagonal, so
topLeft = 0
. - For the bottom-right diagonal, only
1
is on the diagonal, sobottomRight = 1
. answer[0][0] = |0 - 1| = 1
- Update the
answer
matrix:
- There is no top-left diagonal, so
answer = [ [1, 0, 0], [0, 0, 0], [0, 0, 0] ]
- Move to cell
(0, 1)
:- Again, no top-left diagonal, so
topLeft = 0
. - The bottom-right diagonal has
1
and6
, sobottomRight = 2
. answer[0][1] = |0 - 2| = 2
- Update the
answer
matrix:
- Again, no top-left diagonal, so
answer = [ [1, 2, 0], [0, 0, 0], [0, 0, 0] ]
Now we'll do the same for cell (1,1)
, which has both top-left and bottom-right diagonals:
- Inspect the cell
(1, 1)
:- The top-left diagonal contains
4
and1
(sotopLeft[r][c] = 2
). - The bottom-right diagonal contains only
1
, hencebottomRight[r][c] = 1
. answer[1][1] = |2 - 1| = 1
.
- The top-left diagonal contains
Update the answer
matrix:
answer = [ [1, 2, 0], [0, 1, 0], [0, 0, 0] ]
- Continue the process for each cell, calculating the unique counts on both diagonals and computing their absolute difference.
After completing this process for all cells, we would obtain the final answer
matrix:
answer = [ [1, 2, 1], [1, 1, 0], [1, 0, 0] ]
Each step of the process follows the explanation in the solution approach, utilizing the property of sets to count unique elements along the top-left and bottom-right diagonals for each cell and calculating the absolute difference between these unique counts for the answer
matrix.
Solution Implementation
1class Solution:
2 def differenceOfDistinctValues(self, grid: List[List[int]]) -> List[List[int]]:
3 # Get the grid dimensions.
4 rows, cols = len(grid), len(grid[0])
5
6 # Initialize the answer grid with zeros, matching the input grid dimensions.
7 answer_grid = [[0] * cols for _ in range(rows)]
8
9 # Iterate over each cell in the grid.
10 for row in range(rows):
11 for col in range(cols):
12 # Initialize variables for traversing diagonally up-left.
13 x_up, y_up = row, col
14 unique_values_upleft = set() # To store unique values seen so far up-left.
15
16 # Traverse diagonally to the top-left corner, collecting unique values.
17 while x_up > 0 and y_up > 0:
18 x_up, y_up = x_up - 1, y_up - 1
19 unique_values_upleft.add(grid[x_up][y_up])
20
21 # Count the unique values in the top-left diagonal.
22 count_upleft = len(unique_values_upleft)
23
24 # Reset the variables for traversing diagonally down-right.
25 x_down, y_down = row, col
26 unique_values_downright = set() # To store unique values seen so far down-right.
27
28 # Traverse diagonally to the bottom-right corner, collecting unique values.
29 while x_down + 1 < rows and y_down + 1 < cols:
30 x_down, y_down = x_down + 1, y_down + 1
31 unique_values_downright.add(grid[x_down][y_down])
32
33 # Count the unique values in the bottom-right diagonal.
34 count_downright = len(unique_values_downright)
35
36 # Calculate the absolute difference and update the value in the answer grid.
37 answer_grid[row][col] = abs(count_upleft - count_downright)
38
39 # Return the answer grid populated with differences of distinct values.
40 return answer_grid
41
42# Notes:
43# 1. The variable names have been improved for readability.
44# 2. Added comments to explain each section of code.
45# 3. The code logic and method names are unchanged since the request was only to rewrite the code with better variable naming and add comments.
46# 4. Used zero-indexed while loops for traversing the diagonals to correctly access the grid indices.
47
1class Solution {
2 public int[][] differenceOfDistinctValues(int[][] grid) {
3 // Get the number of rows and columns in the grid.
4 int rowCount = grid.length, colCount = grid[0].length;
5 // Initialize the answer grid with the same dimensions.
6 int[][] answerGrid = new int[rowCount][colCount];
7
8 // Iterate over each cell in the grid.
9 for (int i = 0; i < rowCount; ++i) {
10 for (int j = 0; j < colCount; ++j) {
11 // Compute the distinct count in the top-left diagonal direction.
12 int distinctCountTopLeft = calculateDistinctCount(grid, i, j, -1);
13 // Compute the distinct count in the bottom-right diagonal direction.
14 int distinctCountBottomRight = calculateDistinctCount(grid, i, j, 1);
15 // Compute the absolute difference of the distinct counts in both diagonal directions.
16 answerGrid[i][j] = Math.abs(distinctCountTopLeft - distinctCountBottomRight);
17 }
18 }
19
20 // Return the filled answer grid.
21 return answerGrid;
22 }
23
24 // Helper method to calculate the distinct count in a diagonal direction.
25 private int calculateDistinctCount(int[][] grid, int row, int col, int direction) {
26 // Create a set to keep track of the distinct values seen.
27 Set<Integer> distinctValues = new HashSet<>();
28 // Continue moving in the diagonal direction until the grid boundaries are reached.
29 while (row >= 0 && col >= 0 && row < grid.length && col < grid[0].length) {
30 // Add the current value to the set of distinct values.
31 distinctValues.add(grid[row][col]);
32 // Move in the diagonal direction specified by 'direction'.
33 row += direction;
34 col += direction;
35 }
36 // Return the size of the set, i.e., the number of distinct values.
37 return distinctValues.size();
38 }
39}
40
1class Solution {
2public:
3 vector<vector<int>> differenceOfDistinctValues(vector<vector<int>>& grid) {
4 int rows = grid.size(); // Number of rows in the input grid
5 int cols = grid[0].size(); // Number of columns in the input grid
6 vector<vector<int>> answer(rows, vector<int>(cols));
7
8 // Iterate over every cell in the grid
9 for (int i = 0; i < rows; ++i) {
10 for (int j = 0; j < cols; ++j) {
11 unordered_set<int> topLeftValues; // Set to store distinct values in the top-left diagonal
12 unordered_set<int> bottomRightValues; // Set to store distinct values in the bottom-right diagonal
13
14 // Traverse the top-left diagonal from the current cell
15 for (int x = i, y = j; x >= 0 && y >= 0; --x, --y) {
16 topLeftValues.insert(grid[x][y]);
17 }
18
19 // Count distinct values in the top-left diagonal from the current cell
20 int topLeftCount = topLeftValues.size();
21
22 // Traverse the bottom-right diagonal from the current cell
23 for (int x = i, y = j; x < rows && y < cols; ++x, ++y) {
24 bottomRightValues.insert(grid[x][y]);
25 }
26
27 // Count distinct values in the bottom-right diagonal from the current cell
28 int bottomRightCount = bottomRightValues.size();
29
30 // Store the absolute difference of the counts in the answer grid
31 answer[i][j] = abs(topLeftCount - bottomRightCount);
32 }
33 }
34 return answer; // Return the final grid containing absolute differences
35 }
36};
37
1function differenceOfDistinctValues(grid: number[][]): number[][] {
2 // Get the dimensions of the grid
3 const rows = grid.length;
4 const columns = grid[0].length;
5
6 // Initialize an answer grid of the same dimensions with zeroes
7 const answerGrid: number[][] = Array.from({ length: rows }, () => Array(columns).fill(0));
8
9 // Iterate over each cell of the grid
10 for (let i = 0; i < rows; ++i) {
11 for (let j = 0; j < columns; ++j) {
12 // Initialize row and column index for top-left diagonal
13 let rowTopLeft = i;
14 let colTopLeft = j;
15
16 // Create a set to store unique values in the top-left diagonal
17 const topLeftSet = new Set<number>();
18
19 // Traverse the top-left diagonal
20 while (rowTopLeft > 0 && colTopLeft > 0) {
21 topLeftSet.add(grid[--rowTopLeft][--colTopLeft]);
22 }
23
24 // Count distinct values in the top-left diagonal
25 const topLeftDistinctCount = topLeftSet.size;
26
27 // Initialize row and column index for bottom-right diagonal
28 let rowBottomRight = i;
29 let colBottomRight = j;
30
31 // Create a set to store unique values in the bottom-right diagonal
32 const bottomRightSet = new Set<number>();
33
34 // Traverse the bottom-right diagonal
35 while (rowBottomRight + 1 < rows && colBottomRight + 1 < columns) {
36 bottomRightSet.add(grid[++rowBottomRight][++colBottomRight]);
37 }
38
39 // Count distinct values in the bottom-right diagonal
40 const bottomRightDistinctCount = bottomRightSet.size;
41
42 // Calculate the absolute difference of distinct values in both diagonals
43 // and assign it to the corresponding cell in the answer grid
44 answerGrid[i][j] = Math.abs(topLeftDistinctCount - bottomRightDistinctCount);
45 }
46 }
47
48 // Return the answer grid with the differences
49 return answerGrid;
50}
51
Time and Space Complexity
Time Complexity
The time complexity of the code provided is primarily determined by the two nested loops, each iterating over the dimensions of the grid, and the two while loops inside the nested loops. The outer loops run m * n
times where m
is the number of rows and n
is the number of columns in the grid (m
and n
can be considered separately if not square). The inner while loops iterate at worst from 0
to i
for the top-left diagonal elements, and from i
to m
for the bottom-right diagonal elements (and similarly for j
and n
). This gives us two arithmetic progressions counting down and up respectively. The sum of operations due to these internal while loops corresponds to the sum of two arithmetic series, which is effectively O(m + n)
for each outer loop iteration. Therefore, the total time complexity is roughly O((m * n) * (m + n))
, which can also be represented as O(m^2 * n + m * n^2)
when m and n are different.
Space Complexity
The space complexity is O(m * n)
due to the auxiliary space required for the ans
list which is the same size as the grid
. Additionally, the set s
takes up space, but since it is overwritten in each iteration of the loops rather than accumulated, the maximum space it uses at any given time is the size of the largest number of distinct elements on a diagonal, which is at most min(m, n)
. This does not change the overall space complexity, which remains O(m * n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!