Lucky Numbers in a Matrix

Difficulty: Easy | Acceptance: 80.00% | Paid: No Topics: Array, Matrix

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.

• Examples
• Constraints
• Brute Force
• Pre-computation

Examples

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.

Example 3

Input: matrix = [[7,8],[1,2]]
Output: [7]
Explanation: 7 is the only lucky number since it is the minimum in its row and the maximum in its column.

Constraints

m == matrix.length
n == matrix[i].length
1 <= m, n <= 50
1 <= matrix[i][j] <= 10⁵
All the elements in the matrix are distinct.

Brute Force

Intuition For every element in the matrix, we can explicitly check if it is the minimum element in its row and the maximum element in its column.

Steps

• Iterate through every element in the matrix using nested loops.
• For the current element matrix[i][j], iterate through row i to verify it is the minimum value.
• Iterate through column j to verify it is the maximum value.
• If both conditions are met, add the element to the result list.

class Solution:
    def luckyNumbers(self, matrix: list[list[int]]) -> list[int]:
        m, n = len(matrix), len(matrix[0])
        lucky_nums = []
        
        for i in range(m):
            for j in range(n):
                val = matrix[i][j]
                is_row_min = True
                is_col_max = True
                
                # Check if val is the minimum in row i
                for k in range(n):
                    if matrix[i][k] < val:
                        is_row_min = False
                        break
                
                if not is_row_min:
                    continue
                    
                # Check if val is the maximum in column j
                for k in range(m):
                    if matrix[k][j] > val:
                        is_col_max = False
                        break
                
                if is_col_max:
                    lucky_nums.append(val)
                    
        return lucky_nums

Complexity

• Time: O(m * n * (m + n))
• Space: O(1)
• Notes: We scan the row and column for every single element, leading to repeated work.

Pre-computation

Intuition We can optimize by pre-calculating the minimum value for each row and the maximum value for each column in a single pass. Then, we simply check if an element matches both pre-computed values.

Steps

• Create an array row_mins of size m initialized to infinity, and an array col_maxs of size n initialized to negative infinity.
• Iterate through the matrix once. For each element matrix[i][j], update row_mins[i] and col_maxs[j].
• Iterate through the matrix again. If matrix[i][j] equals row_mins[i] and col_maxs[j], add it to the result.

class Solution:
    def luckyNumbers(self, matrix: list[list[int]]) -> list[int]:
        m, n = len(matrix), len(matrix[0])
        row_mins = [float('inf')] * m
        col_maxs = [float('-inf')] * n
        
        # Precompute row minimums and column maximums
        for i in range(m):
            for j in range(n):
                row_mins[i] = min(row_mins[i], matrix[i][j])
                col_maxs[j] = max(col_maxs[j], matrix[i][j])
        
        # Find lucky numbers
        lucky_nums = []
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == row_mins[i] and matrix[i][j] == col_maxs[j]:
                    lucky_nums.append(matrix[i][j])
                    
        return lucky_nums

Complexity

• Time: O(m * n)
• Space: O(m + n)
• Notes: We trade extra space for row and column storage to achieve linear time complexity.