Abstract / Summary

Find the difference between the counts of unique numbers on the main and anti diagonals of a square matrix.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 69% (30k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Matrix

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method differenceOfDistinctValues. The method receives a two-dimensional list grid and returns a new matrix of the same dimensions. For each cell, it computes the absolute difference between the number of distinct values encountered on the top-left diagonal (excluding the cell itself) and the number of distinct values on the bottom-right diagonal (also excluding the cell). The result for every position is stored in a pre-allocated matrix and finally returned.

Initialization of Dimensions and Result Matrix

The first step extracts the width and height of the input grid:

width  = len(grid[0])
height = len(grid)

A result matrix of identical size is created with None placeholders:

result = [ [ None ] * width for y in range(height)]

Pre-allocating the matrix avoids repeated list growth operations during the main computation.

Main Traversal Loop

Two nested for loops iterate over every coordinate (y, x) in the grid:

for y in range(height):
    for x in range(width):
        ...

Inside the inner loop the algorithm isolates the work for a single cell.

Collecting Distinct Values on the Top-Left Diagonal

A local set a gathers distinct values encountered while moving diagonally upward and leftward from the current cell. The loop stops when either the column index reaches zero or the row index reaches zero, ensuring the traversal stays within bounds:

a  = set()
ax = x
ay = y
while ax > 0 and ay > 0:
    ax -= 1
    ay -= 1
    a.add(grid[ay][ax])

Because the loop condition checks both ax and ay before decrementing, the code correctly handles cells located on the first row or first column, where the top-left diagonal is empty. In such cases the set remains empty, and its length is zero.

Collecting Distinct Values on the Bottom-Right Diagonal

A second set b accumulates distinct values while moving diagonally downward and rightward. The loop condition ensures the indices never exceed the grid limits:

b  = set()
bx = x
by = y
while bx < width - 1 and by < height - 1:
    bx += 1
    by += 1
    b.add(grid[by][bx])

When the current cell lies on the last row or last column, the condition fails immediately, leaving b empty. This correctly captures the edge case where there is no bottom-right diagonal.

Computing the Absolute Difference

After both sets are populated, the method calculates the absolute difference of their sizes and stores it in the result matrix:

result[y][x] = abs(len(a) - len(b))

The use of abs guarantees a non-negative integer for every cell, regardless of which diagonal contains more distinct values.

Return Value

Finally, the fully populated matrix is returned:

return result

The returned structure mirrors the shape of the input grid, providing a direct mapping from each original cell to its computed difference.

Edge Cases Handled

The algorithm gracefully manages several boundary conditions:

• A grid consisting of a single cell results in both diagonal sets being empty, yielding a difference of zero for that cell.
• Grids with a single row or a single column cause one of the diagonal traversals to terminate immediately, leaving the corresponding set empty while the other diagonal may still collect values.
• Cells positioned on the outer edges of the grid never attempt to access indices outside the valid range because the while-loop conditions explicitly prevent out-of-bounds moves.

Performance Optimizations Observed

The code incorporates a few optimizations that reduce overhead:

• The result matrix is allocated once before the main loops, avoiding repeated list appends or concatenations.
• Local variables (ax, ay, bx, by) are used inside the diagonal traversals, minimizing attribute lookups on the outer loop indices.
• Sets are employed to automatically filter duplicate values, eliminating the need for explicit checks during diagonal walks.
• The while-loops increment or decrement indices in place, which is more efficient than constructing new coordinate tuples on each iteration.

These choices collectively keep the execution tight, especially for grids of moderate size, by limiting memory allocations and leveraging Python’s built-in data structures for fast membership handling.

Imagine a large square board filled with colorful blocks, just like a grid on a sheet of graph paper. This program wants to help you draw a new board next to the original one. To fill in any spot on this new board, the program looks at the spot you chose on the original board and starts walking diagonally.

First, the program walks toward the top left corner of the board, gathering up all the different colors it sees along that path and putting them into a little basket. Then, the program goes back to your spot and walks toward the bottom right corner, gathering up all the different colors it finds on that path and putting them into a second basket.

Once both baskets are full, the program counts how many items are inside each one. It hides all the duplicate colors so that only the unique ones remain. Finally, the program checks the difference between how many unique colors are in the first basket and how many are in the second basket. The number it finds after subtracting the two becomes the value it writes down in the new board at that same spot. It does this for every single square on the board until the whole job is finished.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster			Java	C++		Python	TS
	WalkCCC			Java	C++		Python
	leetcode.ca			Java	C++	Go	Python	TS
	Progiez			Java	C++		Python
github	charles-wangkai			Java
	everthis	JS
	fsq		Rust
	JoshCrozier	JS
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	Rust
JoshCrozier	JavaScript

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality