Lucky Numbers in a Matrix — Solution in Python, Java & C++
Lucky Numbers in a Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Lucky Numbers in a Matrix is an easy coding problem on arrays and matrix, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Matrix
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an m × n matrix of distinct numbers, return all the lucky numbers, in row order.
A lucky number is an element that is the minimum of its row and the maximum of its column.
Example 1
Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the smallest in its row and the largest in its column.
Example 2
Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output: [12]
Example 3
Input: matrix = [[7,8],[1,2]]
Output: [7]
Constraints
1 <= matrix.length, matrix[i].length <= 81 <= matrix[i][j] <= 100000All elements are distinct.
Hints for Lucky Numbers in a Matrix
Hint 1
Find the minimum of each row, then check whether it also dominates its column.
Hint 2
Because the values are distinct, at most one lucky number can exist — but scanning every row is still the clearest way to find it.
Hint 3
Alternatively, intersect the set of row minima with the set of column maxima.
How to solve Lucky Numbers in a Matrix
Collect the minimum of every row and the maximum of every column; a lucky number is in both sets.
Approach
- Build the set of row minima.
- Build the set of column maxima.
- Walk the matrix in row order and emit values in both sets.
Why it works
The definition is exactly the intersection of those two properties, and distinct values mean a set lookup identifies the cell unambiguously.
Complexity
- Time —
O(m · n) - Space —
O(m + n)
Pitfalls
- At most one lucky number can exist when values are distinct, but the scan is still the clearest formulation.
Reference solution
Python
def luckyNumbers(matrix):
row_min = {min(row) for row in matrix}
col_max = {max(col) for col in zip(*matrix)}
return [v for row in matrix for v in row if v in row_min and v in col_max]Java
public static int[] luckyNumbers(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
List<Integer> out = new ArrayList<>();
for (int r = 0; r < m; r++) {
int minC = 0;
for (int c = 1; c < n; c++) {
if (matrix[r][c] < matrix[r][minC]) minC = c;
}
boolean isMax = true;
for (int rr = 0; rr < m; rr++) {
if (matrix[rr][minC] > matrix[r][minC]) { isMax = false; break; }
}
if (isMax) out.add(matrix[r][minC]);
}
int[] res = new int[out.size()];
for (int i = 0; i < res.length; i++) res[i] = out.get(i);
return res;
}C++
vector<int> luckyNumbers(vector<vector<int>>& matrix) {
int m = (int) matrix.size(), n = (int) matrix[0].size();
vector<int> out;
for (int r = 0; r < m; r++) {
int minC = 0;
for (int c = 1; c < n; c++) {
if (matrix[r][c] < matrix[r][minC]) minC = c;
}
bool isMax = true;
for (int rr = 0; rr < m; rr++) {
if (matrix[rr][minC] > matrix[r][minC]) { isMax = false; break; }
}
if (isMax) out.push_back(matrix[r][minC]);
}
return out;
}JavaScript
var luckyNumbers = function(matrix) {
const m = matrix.length, n = matrix[0].length;
const out = [];
for (let r = 0; r < m; r++) {
let minC = 0;
for (let c = 1; c < n; c++) {
if (matrix[r][c] < matrix[r][minC]) minC = c;
}
let isMax = true;
for (let rr = 0; rr < m; rr++) {
if (matrix[rr][minC] > matrix[r][minC]) { isMax = false; break; }
}
if (isMax) out.push(matrix[r][minC]);
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal