EASY
DATA STRUCTURES AND ALGORITHMS

# How to Solve Lucky Numbers in a Matrix

Written By ## Lucky Numbers in a Matrix Introduction

The Lucky Numbers in a Matrix problem asks us to return all lucky numbers in the given matrix. We can easily solve this by initializing an empty list to track lucky numbers and iterating through the matrix, checking if each value satisfies the conditions to become a "lucky number".

## Lucky Numbers in a Matrix 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 Inputs and Outputs

#### Example 1

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

#### Example 2

Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output: 

#### Example 2

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

## Lucky Numbers in a Matrix Solutions

To solve this problem, we can iterate over each row of the matrix and identify the minimum element in each row. We can then check if the minimum element is also the maximum element in its corresponding column. If it is then we consider it a lucky number.

To implement this, we start by initializing an empty list to store the lucky numbers. We iterate over each row of the matrix using a for loop. Within each row, we can keep track of the minimum element and its corresponding index. We update the minimum element whenever we find a smaller value. Once we have the minimum elemenent of the row, we traverse the corresponding column and check if any element is greater than the minimum value. If we find such an element, we know that the current number is not a lucky number, so we move on to the next row. However, if the minimum value is the maximum value in its column, we add it to the list of lucky numbers. Finally we return the list of lucky numbers.

``````def luckyNumbers(matrix):
# Initialize the list to store the lucky numbers
lucky_nums = []

# Iterate through each element in the matrix
for i in range(len(matrix)):
min_val = min(matrix[i])  # Find the minimum element in the current row

# Check if the current element is the maximum in its column
for j in range(len(matrix)):
max_val = max(matrix[k][j] for k in range(len(matrix)))  # Find the maximum element in the current column
if matrix[i][j] == min_val and matrix[i][j] == max_val:
lucky_nums.append(matrix[i][j])  # Add the lucky number to the list

return lucky_nums

matrix = [[3, 7, 8], [9, 11, 13], [15, 16, 17]]
result = luckyNumbers(matrix)
print(result)  # Output should be ``````

#### Time/Space Complexity Analysis

• Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the matrix.
• Space Complexity: O(1), as we use a constant amount of extra space.