LeetCode 1380. Lucky Numbers in a Matrix

Description

https://leetcode.com/problems/find-common-characters/

Given a m * 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 1:

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

Example 2:

Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output: [12]
Explanation: 12 is the only lucky number since it is the minimum in its row and the maximum in its column.

Example 3:

Input: matrix = [[7,8],[1,2]]
Output: [7]

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= n, m <= 50
  • 1 <= matrix[i][j] <= 10^5.
  • All elements in the matrix are distinct.

Explanation

Find minimum numbers of each row and maximum numbers of each column, and then check which number in the matrix matches the minimum numbers in the row and maximum number in the column.

Python Solution

class Solution:
    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
        row_min_numbers = {}
                
        for i in range(len(matrix)):
            row_min_numbers[i] = min(matrix[i])
            
        columns = defaultdict(list)
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                columns[j].append(matrix[i][j])
        
        
        column_max_numbers = {}
        for key, value in columns.items():            
            column_max_numbers[key] = max(value)
        
        
        results = []
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == row_min_numbers[i] and matrix[i][j] == column_max_numbers[j]:                    
                    results.append(matrix[i][j])
                    
        
        return results
        
  • Time Complexity: O(N^2)
  • Space Complexity: O(N)

Leave a Reply

Your email address will not be published.