Lucky Numbers in a Matrix
Easy · Matrix · Array · Matrix
Problem
You are given an m x n matrix of distinct integers. A value is lucky when it is the smallest value in its row and, at the same time, the largest value in its column.
Return all lucky numbers in the matrix, in any order.
Examples
Input: matrix = [[9,4,6],[12,10,11],[3,8,2]] Output: [10]
10 is the smallest in row 1 and the largest in column 1.
Input: matrix = [[1,5],[6,2]] Output: []
The row minimums are 1 and 2, and neither is the largest in its column.
Input: matrix = [[7,8],[1,2]] Output: [7]
7 is the smallest in row 0 and the largest in column 0.
Constraints
- m == len(matrix), n == len(matrix[i])
- 1 <= m, n <= 50
- 1 <= matrix[i][j] <= 10^5
- All values in the matrix are distinct
Approaches
- Check every cell — time O(m · n · (m + n)), space O(1) beyond the answer
Follow-up
What if values can repeat? Then several cells can tie for a row minimum and a column maximum at once, and the two-number shortcut no longer tells you how many there are. Precompute every row minimum and column maximum and test each cell; see the second use case.
Related problems
Start free on Cariara · Coding problems · System design studio
