Lucky Numbers in a Matrix
Precompute per-row minimum and per-column maximum; an element is "lucky" iff it's both.
4 min read
matrix hashing
Problem#
A “lucky number” is an element that is the minimum of its row and the maximum of its column. Return all lucky numbers in the matrix in any order.
Examples#
[[3,7,8],[9,11,13],[15,16,17]]→[15][[1,10,4,2],[9,3,8,7],[15,16,17,12]]→[12][[7,8],[1,2]]→[7]
Constraints#
1 <= m, n <= 50,1 <= matrix[i][j] <= 10^5. All elements distinct.
Approach#
Compute rowMin[i] = min of row i and colMax[j] = max of column j. Walk every cell; if matrix[i][j] equals both, add it.
Solution#
class Solution {public: vector<int> luckyNumbers(vector<vector<int>>& matrix) { int m = matrix.size(), n = matrix[0].size(); vector<int> rowMin(m, INT_MAX), colMax(n, INT_MIN); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) { rowMin[i] = min(rowMin[i], matrix[i][j]); colMax[j] = max(colMax[j], matrix[i][j]); } vector<int> ans; for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) if (matrix[i][j] == rowMin[i] && matrix[i][j] == colMax[j]) ans.push_back(matrix[i][j]); return ans; }};import "math"
func luckyNumbers(matrix [][]int) []int { m, n := len(matrix), len(matrix[0]) rowMin := make([]int, m) colMax := make([]int, n) for i := range rowMin { rowMin[i] = math.MaxInt32 } for j := range colMax { colMax[j] = math.MinInt32 } for i := 0; i < m; i++ { for j := 0; j < n; j++ { if matrix[i][j] < rowMin[i] { rowMin[i] = matrix[i][j] } if matrix[i][j] > colMax[j] { colMax[j] = matrix[i][j] } } } var ans []int for i := 0; i < m; i++ { for j := 0; j < n; j++ { if matrix[i][j] == rowMin[i] && matrix[i][j] == colMax[j] { ans = append(ans, matrix[i][j]) } } } return ans}from typing import List
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)] ans: List[int] = [] for i in range(m): for j in range(n): if matrix[i][j] == row_min[i] and matrix[i][j] == col_max[j]: ans.append(matrix[i][j]) return ansfunction luckyNumbers(matrix) { const m = matrix.length, n = matrix[0].length; const rowMin = new Array(m).fill(Infinity); const colMax = new Array(n).fill(-Infinity); for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (matrix[i][j] < rowMin[i]) rowMin[i] = matrix[i][j]; if (matrix[i][j] > colMax[j]) colMax[j] = matrix[i][j]; } } const ans = []; for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (matrix[i][j] === rowMin[i] && matrix[i][j] === colMax[j]) { ans.push(matrix[i][j]); } } } return ans;}class Solution { public List<Integer> luckyNumbers(int[][] matrix) { int m = matrix.length, n = matrix[0].length; int[] rowMin = new int[m]; int[] colMax = new int[n]; Arrays.fill(rowMin, Integer.MAX_VALUE); Arrays.fill(colMax, Integer.MIN_VALUE); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] < rowMin[i]) rowMin[i] = matrix[i][j]; if (matrix[i][j] > colMax[j]) colMax[j] = matrix[i][j]; } } List<Integer> ans = new ArrayList<>(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == rowMin[i] && matrix[i][j] == colMax[j]) { ans.add(matrix[i][j]); } } } return ans; }}function luckyNumbers(matrix: number[][]): number[] { const m = matrix.length, n = matrix[0].length; const rowMin: number[] = new Array(m).fill(Infinity); const colMax: number[] = new Array(n).fill(-Infinity); for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (matrix[i][j] < rowMin[i]) rowMin[i] = matrix[i][j]; if (matrix[i][j] > colMax[j]) colMax[j] = matrix[i][j]; } } const ans: number[] = []; for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (matrix[i][j] === rowMin[i] && matrix[i][j] === colMax[j]) { ans.push(matrix[i][j]); } } } return ans;}Editorial#
Two passes — one to gather row mins and column maxes (folded into one pass) and one to test each cell. Distinct values guarantee at most one such number, but the algorithm doesn’t depend on that.
Complexity#
- Time: O(m*n).
- Space: O(m + n).
Concept revision#
Related#