💬 Discord
Sign In
NeetCode #894LC-1380EasyMath & Geometry
← Back to All Problems

#894 · #1380 · Lucky Numbers in a Matrix(矩阵中的幸运数)

📌 Problem Statement & Constraints

Given an m x n matrix of distinct integers, return all lucky numbers in any order. A lucky number is an element that is the minimum of its row and simultaneously the maximum of its column. Constraints: 1 <= m, n <= 50, 1 <= matrix[i][j] <= 10^5, and all elements are distinct.

💡 Core Algorithmic Approaches

  1. Precompute the minimum of every row and the maximum of every column.
  2. Scan every cell and keep those that equal both its row minimum and its column maximum.
  3. Distinctness is not required for correctness, but the problem guarantees it, which makes the answer unique.
  4. There is at most one lucky number under the distinctness guarantee, but the signature returns a list.

💻 Benchmark Python3 Implementation

class Solution:
    def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        row_min = [min(row) for row in matrix]
        col_max = [max(matrix[i][j] for i in range(m)) for j in range(n)]
        res = []
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == row_min[i] and matrix[i][j] == col_max[j]:
                    res.append(matrix[i][j])
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): the row minima, column maxima and final scan are each linear in the cell count.
💾 Space Complexity
O(m + n): the two auxiliary arrays.

⚠️ Interview Pitfalls & Follow-ups

  • Swapping the two roles: a lucky number is the row minimum and the column maximum, not the reverse.
  • Returning a single integer instead of a list: the signature requires a list even when the answer is unique.
  • Recomputing min(row) and max(col) inside the double loop: that degrades the complexity to O(m * n * (m + n)).
  • Assuming the answer must exist: some matrices have no lucky number, so an empty list is a valid result.