DSA Graphs

Lucky Numbers in a Matrix

Precompute per-row minimum and per-column maximum; an element is "lucky" iff it's both.

Easy
Time O(m*n) Space O(m + n)
LeetCode
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#

Lucky Numbers in a Matrix
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;
}
};

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#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.