Lucky Numbers in a Matrix Introduction
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
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: [15]
Example 2
Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output: [12]
Example 2
Input: matrix = [[7,8],[1,2]]
Output: [7]
Lucky Numbers in a Matrix Solutions
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[0])):
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 [15]1def luckyNumbers(matrix):
2 # Initialize the list to store the lucky numbers
3 lucky_nums = []
4
5 # Iterate through each element in the matrix
6 for i in range(len(matrix)):
7 min_val = min(matrix[i]) # Find the minimum element in the current row
8
9 # Check if the current element is the maximum in its column
10 for j in range(len(matrix[0])):
11 max_val = max(matrix[k][j] for k in range(len(matrix))) # Find the maximum element in the current column
12 if matrix[i][j] == min_val and matrix[i][j] == max_val:
13 lucky_nums.append(matrix[i][j]) # Add the lucky number to the list
14
15 return lucky_nums
16
17matrix = [[3, 7, 8], [9, 11, 13], [15, 16, 17]]
18result = luckyNumbers(matrix)
19print(result) # Output should be [15]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.
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
