Lucky Numbers in a Matrix
Problem
Given an m x n matrix of distinct integers, return all lucky numbers in any order. A lucky number is a value that is the smallest element in its row and at the same time the largest element in its column.
matrix = [[3,7,8],[9,11,13],[15,16,17]][15]def lucky_numbers(matrix):
row_min = {min(row) for row in matrix}
col_max = {max(col) for col in zip(*matrix)}
return list(row_min & col_max)function luckyNumbers(matrix) {
const rowMin = matrix.map(row => Math.min(...row));
const colMax = matrix[0].map((_, j) =>
Math.max(...matrix.map(row => row[j])));
return rowMin.filter(v => colMax.includes(v));
}class Solution {
public List<Integer> luckyNumbers(int[][] matrix) {
Set<Integer> rowMin = new HashSet<>();
for (int[] row : matrix) {
int lo = row[0];
for (int v : row) lo = Math.min(lo, v);
rowMin.add(lo);
}
List<Integer> res = new ArrayList<>();
for (int j = 0; j < matrix[0].length; j++) {
int hi = matrix[0][j];
for (int[] row : matrix) hi = Math.max(hi, row[j]);
if (rowMin.contains(hi)) res.add(hi);
}
return res;
}
}vector<int> luckyNumbers(vector<vector<int>>& matrix) {
set<int> rowMin;
for (auto& row : matrix)
rowMin.insert(*min_element(row.begin(), row.end()));
vector<int> res;
for (int j = 0; j < (int)matrix[0].size(); j++) {
int hi = matrix[0][j];
for (auto& row : matrix) hi = max(hi, row[j]);
if (rowMin.count(hi)) res.push_back(hi);
}
return res;
}Explanation
A lucky number has to satisfy two conditions at once: it must be the smallest value in its own row, and the largest value in its own column. Instead of checking every cell against its whole row and column repeatedly, we precompute the two facts we care about.
First, walk each row and record its minimum. Every row contributes exactly one candidate, because only the row's smallest element can ever be a lucky number. Collect these into a set of row minimums.
Next, walk each column and record its maximum. A lucky number must also be the biggest in its column, so any answer has to appear among these column maximums.
Finally, the lucky numbers are exactly the values that show up in both groups — the intersection of "row minimums" and "column maximums". Because the matrix has distinct integers, this intersection holds at most one value, but the same logic returns all of them in general.
Example: [[3,7,8],[9,11,13],[15,16,17]]. Row minimums are 3, 9, 15. Column maximums are 15, 16, 17. The only value in both lists is 15, so the answer is [15].