algoadvance

1380. Lucky Numbers in a Matrix

Given a 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.

Clarifying Questions

1. Input Constraints:
   • Is it guaranteed that each row and each column will contain distinct numbers?
   • What should be returned if no lucky numbers are found in the matrix?
2. Output Format:
   • Should the lucky numbers be returned in any particular order?

Strategy

To determine the lucky numbers in a matrix, we can follow these steps:

1. Find Minimums in Each Row:
   • Traverse each row to find the minimum element and store its value along with its column index.
2. Verify Maximum in the Column:
   • For each element found in step 1, verify if it’s the maximum element in its respective column.

Here’s a step-by-step breakdown of the approach:

1. Iterate through each row and record the minimum value along with its column index.
2. For each minimum value found, check if it is the maximum value in its column.
3. Return the list of all elements that satisfy both conditions.

Time Complexity

• Finding minimums in each row will take O(m * n), where m is the number of rows and n is the number of columns.
• Checking maximums in the columns can take up to O(m * n) in the worst case.
• Therefore, the overall time complexity is O(m * n).

Code

Here is the Python code that implements the above strategy:

def luckyNumbers(matrix):
    min_in_rows = []
    m, n = len(matrix), len(matrix[0])
    
    # Step 1: Find the minimum in each row
    for i in range(m):
        min_val = min(matrix[i])
        min_index = matrix[i].index(min_val)
        min_in_rows.append((min_val, min_index))
    
    # Step 2: Verify if the minimums are maximum in their respective columns
    lucky_nums = []
    for (min_val, col_index) in min_in_rows:
        is_lucky = True
        for row in range(m):
            if matrix[row][col_index] > min_val:
                is_lucky = False
                break
        if is_lucky:
            lucky_nums.append(min_val)
    
    return lucky_nums

Example Usage

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

print(luckyNumbers(matrix))  # Output: [15]

In this example:

• The minimums in each row are 3, 9, and 15.
• Among these, only 15 is the maximum in its column.

Conclusion

The provided code correctly identifies the lucky numbers in the given matrix by ensuring that each candidate is both a row minimum and column maximum. The approach efficiently checks each condition using nested loops, maintaining a manageable O(m * n) time complexity.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?