Lucky Numbers in a Matrix — LeetCode 1380 Python Solution

The problem

Given an m x n matrix of distinct numbers, return all lucky numbers in the matrix in any order. A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.

Example

Input

matrix = [[3,7,8],[9,11,13],[15,16,17]]

Output

[15]

Explanation

15 is the only lucky number since it is the minimum in its row and the maximum in its column.

Python solution

class Solution:
    def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
        rows = {min(row) for row in matrix}
        cols = {max(col) for col in zip(*matrix)}
        return list(rows & cols)

Complexity

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 1380. Lucky Numbers in a Matrix is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Matrix.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Related problems