Lucky Numbers In A Matrix - Leetcode Solution

Problem Statement:

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.

Solution:

To solve this problem, we need to iterate over the matrix to find the minimum element in each row and maximum element in each column. Then we check if the minimum element in a row is equal to the maximum element in its column. If so, that element is a lucky number.

Here is the step-by-step solution to this problem:

1. Define a list to store the lucky numbers: lucky_numbers = []

2. Iterate over the rows of the matrix for row in matrix:

   2.1. Find the minimum element in the row. row_min = min(row)

   2.2. Find the index of the minimum element in the row. row_min_index = row.index(row_min)

   2.3. Iterate over the columns of the matrix to find the maximum element in the column. column_max = -1 for i in range(len(matrix)): column_max = max(column_max, matrix[i][row_min_index])

   2.4. If the minimum element in the row is equal to the maximum element in its column, it is a lucky number. Append it to the lucky_numbers list. if row_min == column_max: lucky_numbers.append(row_min)

3. Return the list of lucky numbers. return lucky_numbers

Here is the complete Python code:

def luckyNumbers (matrix): lucky_numbers = [] for row in matrix: row_min = min(row) row_min_index = row.index(row_min) column_max = -1 for i in range(len(matrix)): column_max = max(column_max, matrix[i][row_min_index]) if row_min == column_max: lucky_numbers.append(row_min) return lucky_numbers

Time Complexity:

The time complexity of this solution is O(m*n) where m is the number of rows and n is the number of columns in the matrix. This is because we iterate over each element of the matrix once.

Space Complexity:

The space complexity of this solution is O(1) because we only use a fixed number of variables to store the values of minimum element in a row, maximum element in a column, and lucky numbers.

1