Abstract / Summary

Given a matrix and queries, change specified cells to zero and return the number of distinct rows after each query.

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% (80k+ submissions).

Typical patterns to solve this problem:

• Array
• 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 method that transforms a two-dimensional integer array in place. For each column it determines the greatest value present and substitutes every occurrence of -1 with that column-wise maximum. The method finally returns the mutated matrix. The algorithm works directly on the input structure, avoiding the allocation of auxiliary containers.

Key Steps

Determining matrix dimensions

The first two statements capture the number of rows and columns. By storing these values in local variables the code avoids repeated attribute lookups during the nested loops.

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

Column-wise iteration

A for loop iterates over the column index x from 0 to width-1. This outer loop isolates the work that must be performed independently for each column.

for x in range(width):

Computing the column maximum

Inside the column loop a generator expression scans all rows y for the current column x. The built-in max function consumes the generator and returns the highest element. Using a generator expression keeps the memory footprint minimal because values are produced on demand rather than collected in a temporary list.

high = max(matrix[y][x] for y in range(height))

Replacing sentinel values

A second inner loop walks through the rows of the current column. Whenever the cell contains the sentinel -1, it is overwritten with the previously computed maximum. Because the matrix is mutated directly, no additional data structures are required.

for y in range(height):
    if matrix[y][x] == -1:
        matrix[y][x] = high

Returning the result

After all columns have been processed, the method returns the same list object that was supplied as input, now containing the updated values.

return matrix

Edge Cases Handled

The algorithm gracefully handles a matrix that consists of a single row. In that situation height equals 1, the generator expression still iterates over a single element, and any -1 in the sole row is replaced by the only value present in its column.

A single-column matrix is also supported. The outer loop runs once, the inner loops traverse all rows, and the column maximum is correctly identified even when the column contains a mixture of positive numbers and -1.

When a column contains only -1 values, the generator expression still yields -1 for each row, making the maximum equal to -1. Consequently, the replacement step writes -1 back into the same cells, leaving the column unchanged. This behavior matches the expectation that the sentinel should be replaced by the greatest existing value, which in this degenerate case is the sentinel itself.

If a column has no -1 entries, the inner replacement loop performs only the equality check and makes no modifications, preserving the original values.

The code also works correctly when the matrix is empty or when rows are empty. In those scenarios the initial dimension extraction would raise an exception, but such inputs are outside the intended contract of the method, which assumes a well-formed non-empty rectangular matrix.

Performance Optimizations

The implementation leverages several techniques that reduce overhead:

• In-place mutation eliminates the need for a secondary matrix, cutting both memory usage and the cost of copying data.
• Local variable caching of height and width prevents repeated evaluation of len on the same objects inside the loops.
• Generator expression for maximum avoids constructing an intermediate list of column values; the max function consumes the generator directly.
• Two-pass column processing isolates the expensive maximum computation from the conditional replacement, ensuring that the maximum is calculated only once per column rather than repeatedly for each row.

These choices collectively produce a solution that scales efficiently with the size of the input matrix while maintaining a clear and straightforward control flow.

Think of this grid of numbers like a big box filled with smaller containers. Each container holds a specific number, but sometimes one is empty, represented by a negative one.

The goal is to go through every single column of containers one at a time. First, the code looks at all the numbers in that column to find the very biggest one. It carries this biggest number around like a special secret prize. Then, it looks at that same column again. If it sees one of those empty containers, it swaps the empty space for the biggest number found earlier. After finishing one column, the code moves on to the next one and does the exact same thing until every empty space is filled with the big number from its own column.

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++	C#	Go	Python	TS
	Progiez	Java		C++			Python
github	charles-wangkai	Java
	fsq			C++
	JoshCrozier		JS
	varunu28	Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, C#, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
fsq	C++
JoshCrozier	JavaScript
varunu28	Java

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