Domain 1EasyCORE

Lucky Numbers in a Matrix

The problem requires identifying "lucky numbers" in a given matrix. A lucky number is defined as an element that is the minimum in its row and the maximum in its column. The input is a matrix of distinct integers, and the output should be a list of these lucky numbers.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

1380. Lucky Numbers in a Matrix

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 0
Acceptance rate: 70.4%


Problem Breakdown

The problem requires identifying “lucky numbers” in a given matrix. A lucky number is defined as an element that is the minimum in its row and the maximum in its column. The input is a matrix of distinct integers, and the output should be a list of these lucky numbers.

Inputs:

  • A 2D list matrix where each sublist represents a row in the matrix.
  • The matrix dimensions are m x n, with 1 <= m, n <= 50.

Outputs:

  • A list of integers that are lucky numbers in the matrix.

Implicit Constraints:

  • All elements in the matrix are distinct.
  • The matrix is non-empty and contains at least one element.

Intuition

A brute-force approach would involve iterating through each element in the matrix to check if it is the minimum in its row and the maximum in its column. This approach would have a time complexity of O(m * n * (m + n)), which is inefficient given the constraints.

The key insight is to preprocess the matrix to find the minimum values in each row and the maximum values in each column separately. By doing so, we can reduce the problem to checking if an element satisfies both conditions simultaneously, leading to a more efficient solution with a time complexity of O(m * n).

Approach

  1. Preprocess Rows: Iterate through each row and find the minimum value in that row. Store these minimum values in a list called row_mins.
  2. Preprocess Columns: Iterate through each column and find the maximum value in that column. Store these maximum values in a list called col_maxs.
  3. Identify Lucky Numbers: Iterate through each element in the matrix again. For each element, check if it is equal to both the corresponding minimum value in its row (from row_mins) and the corresponding maximum value in its column (from col_maxs). If it satisfies both conditions, add it to the result list.

Complexity Analysis

  • Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. This is because we iterate through the matrix three times: once for finding row minimums, once for column maximums, and once for checking lucky numbers.
  • Space Complexity: O(m + n) for storing the row minimums and column maximums.

Solution

def luckyNumbers(matrix):
    if not matrix or not matrix[0]:
        return []

    m, n = len(matrix), len(matrix[0])
    
    # Find the minimum value in each row
    row_mins = [min(row) for row in matrix]
    
    # Find the maximum value in each column
    col_maxs = [max(matrix[row][col] for row in range(m)) for col in range(n)]
    
    lucky_numbers = []
    
    # Check if an element is both a row minimum and a column maximum
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == row_mins[i] == col_maxs[j]:
                lucky_numbers.append(matrix[i][j])
    
    return lucky_numbers

Edge Cases Handled

  • Empty Matrix: The function checks if the matrix is empty at the beginning and returns an empty list immediately.
  • Single Element Matrix: If the matrix contains only one element, that element is trivially a lucky number since it is both the minimum in its row and the maximum in its column.