Lucky Numbers in a Matrix

Problem Description

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.

Key Insights

• A lucky number must satisfy two conditions:
  • It is the minimum in its respective row.
  • It is the maximum in its respective column.
• Since all elements in the matrix are distinct, we can directly compare values without worrying about duplicates.
• The problem can be solved efficiently by iterating through the matrix to gather potential candidates for lucky numbers.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(1) (not counting the output)

Solution

The solution involves iterating through each row of the matrix to find the minimum element, and then checking if that minimum element is the maximum in its respective column. We will maintain a list of lucky numbers that meet these criteria.

1. Loop through each row of the matrix.
2. For each row, identify the minimum element and its column index.
3. Check if this minimum element is the maximum in its column.
4. If both conditions are satisfied, add the element to the list of lucky numbers.

Code Solutions