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:

  1. Is this element the minimum in its row?
  2. 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 built-in Python functions min(), max() and index():

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
        # Find the minimum number in each row
        minRow = [min(row) for row in matrix]

        # Find the maximum number in each column
        maxCol = [max(col) for col in zip(*matrix)]

        # Initialize an empty list for lucky numbers
        lucky_numbers = []

        # Iterate over the range of minRow
        for i in range(len(minRow)):
            # Get the column index of the minimum number in the row i
            col_index = matrix[i].index(minRow[i])

            # Check if the number is also the maximum in its column
            if minRow[i] == maxCol[col_index]:
                # If so, add it to the list of lucky numbers
                lucky_numbers.append(minRow[i])

        # Return the list of lucky numbers
        return lucky_numbers

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 non-zero 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:

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

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

  3. We calculate the difference between the new height and the original height, and add it to a running total.

  4. At the end, the total represents the maximum increase in height that can be achieved.

Let’s see this in Python code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def maxIncreaseKeepingSkyline(self, grid: List[List[int]]) -> int:
        # Find the maximum height in each row
        maxRow = [max(row) for row in grid]

        # Find the maximum height in each column
        maxCol = [max(col) for col in zip(*grid)]

        # Initialize a variable to store total increase
        total_increase = 0

        # Traverse through each cell in the grid
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                # Find the lesser of the maximum height in its row and column
                new_height = min(maxRow[i], maxCol[j])

                # Calculate the difference and add to total increase
                total_increase += new_height - grid[i][j]

        # Return the total increase
        return total_increase

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.