Lucky Numbers in a Matrix
The task at hand is to find the ’lucky numbers’ from a 2D matrix, where a ’lucky number’ is defined as a number that is the minimum in its row and the maximum in its column.
First, let’s try to understand the problem step by step. We need to traverse all the elements in the matrix, and for each element, we have to check two conditions:
 Is this element the minimum in its row?
 Is this element the maximum in its column?
If both conditions are satisfied, the element is a ’lucky number'.
Here is a simple Python solution using list comprehension and the builtin Python functions min(), max() and index():


In this solution, we create two lists: minRow
and maxCol
, representing the minimum number in each row and the maximum number in each column respectively.
We then return the list of numbers which appear in both minRow
and maxCol
. These are the ’lucky numbers’ as they satisfy both conditions defined in the problem.
The zip(*matrix)
in maxCol
is used to transpose the rows and columns, so we can get the maximum of each column.
Finally, matrix[i].index(minRow[i])
is used to get the column index of the minimum number in the row i
.
The time complexity of this solution is O(m*n) where m and n are the number of rows and columns of the matrix. This is because we have to check each element in the matrix once to find the minimums and maximums. The space complexity is O(m+n) as we are storing the minimums and maximums.
We can use this same technique to solve this question  807. Max Increase to Keep City Skyline. In that question, we have to find elements which are maximum in their row & column in the 1st pass. In 2nd pass, we’ve to traverse through the matrix and find the minimum between these 2 maximums and keep storing the difference i.e. count += min(mi[i], mx[j])  matrix[i][j]. That will give us the max increase to keep city skyline.
Identifying Problem Isomorphism
“Max Increase to Keep City Skyline” is related and the approach you mentioned is correct.
The problem statement for “Max Increase to Keep City Skyline” is: “In a 2D grid of size m x n, each cell is a building of certain height. The skyline viewed from top or bottom is the maximum height of each column. The skyline viewed from left or right is the maximum height of each row. Suppose you increase the height of each nonzero building to the maximum possible height without altering the skyline from any side, how much total increase in the height of the buildings can be done?”
The main steps to solve it are:
First, find the maximum height in each row and each column. This gives us the skyline when viewed from left/right and top/bottom respectively.
Then, traverse through each cell in the grid again. For each cell, we determine the lesser of the maximum height in its row and column. This represents the maximum height this building can be increased to without affecting the skyline.
We calculate the difference between the new height and the original height, and add it to a running total.
At the end, the total represents the maximum increase in height that can be achieved.
Let’s see this in Python code:


This approach works because to maintain the skylines from both views, a building’s new height cannot exceed the maximum height in its row or column. Among these two maximums, we have to pick the lesser one to ensure both skylines are not affected. By adding up the increases for each building, we get the total maximum increase.