LeetCode 1380: Lucky Numbers in a Matrix (Row Minimum + Column Maximum)
LeetCode 1380MatrixSimulationToday we solve LeetCode 1380 - Lucky Numbers in a Matrix.
Source: https://leetcode.com/problems/lucky-numbers-in-a-matrix/
English
Problem Summary
A lucky number is an element in the matrix that is the minimum value in its row and the maximum value in its column. Return all lucky numbers in any order.
Key Insight
For each row, only the row minimum can possibly be lucky. So we first find the minimum value and its column index in that row, then verify whether this value is also the maximum in that column.
Algorithm
- Iterate each row.
- Find the minimum element and its column index col.
- Scan all rows at column col to check if any value is greater.
- If none is greater, this row minimum is lucky; add it to answer.
Complexity Analysis
Let m be rows and n be columns.
Time: O(m * n + m * m) in this direct scan form (for each row, one row scan + one column scan).
Space: O(1) extra (excluding output).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public List<Integer> luckyNumbers (int[][] matrix) {
List<Integer> ans = new ArrayList<>();
int m = matrix.length, n = matrix[0].length;
for (int i = 0; i < m; i++) {
int minVal = matrix[i][0], col = 0;
for (int j = 1; j < n; j++) {
if (matrix[i][j] < minVal) {
minVal = matrix[i][j];
col = j;
}
}
boolean isColMax = true;
for (int r = 0; r < m; r++) {
if (matrix[r][col] > minVal) {
isColMax = false;
break;
}
}
if (isColMax) {
ans.add(minVal);
}
}
return ans;
}
}func luckyNumbers(matrix [][]int) []int {
m, n := len(matrix), len(matrix[0])
ans := []int{}
for i := 0; i < m; i++ {
minVal, col := matrix[i][0], 0
for j := 1; j < n; j++ {
if matrix[i][j] < minVal {
minVal = matrix[i][j]
col = j
}
}
isColMax := true
for r := 0; r < m; r++ {
if matrix[r][col] > minVal {
isColMax = false
break
}
}
if isColMax {
ans = append(ans, minVal)
}
}
return ans
}class Solution {
public:
vector<int> luckyNumbers (vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<int> ans;
for (int i = 0; i < m; ++i) {
int minVal = matrix[i][0], col = 0;
for (int j = 1; j < n; ++j) {
if (matrix[i][j] < minVal) {
minVal = matrix[i][j];
col = j;
}
}
bool isColMax = true;
for (int r = 0; r < m; ++r) {
if (matrix[r][col] > minVal) {
isColMax = false;
break;
}
}
if (isColMax) ans.push_back(minVal);
}
return ans;
}
};class Solution:
def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
m, n = len(matrix), len(matrix[0])
ans = []
for i in range(m):
min_val = matrix[i][0]
col = 0
for j in range(1, n):
if matrix[i][j] < min_val:
min_val = matrix[i][j]
col = j
is_col_max = True
for r in range(m):
if matrix[r][col] > min_val:
is_col_max = False
break
if is_col_max:
ans.append(min_val)
return ansvar luckyNumbers = function(matrix) {
const m = matrix.length;
const n = matrix[0].length;
const ans = [];
for (let i = 0; i < m; i++) {
let minVal = matrix[i][0];
let col = 0;
for (let j = 1; j < n; j++) {
if (matrix[i][j] < minVal) {
minVal = matrix[i][j];
col = j;
}
}
let isColMax = true;
for (let r = 0; r < m; r++) {
if (matrix[r][col] > minVal) {
isColMax = false;
break;
}
}
if (isColMax) ans.push(minVal);
}
return ans;
};中文
题目概述
矩阵中的 幸运数 指的是：在所在行里是最小值，同时在所在列里是最大值。返回所有幸运数，顺序不限。
核心思路
每一行只有“行最小值”才可能成为幸运数。因此先在该行找到最小值及其列下标，再验证它是否是这一列的最大值。
算法步骤
- 遍历每一行。
- 找到该行最小值 minVal 和对应列 col。
- 扫描整列 col，若存在比 minVal 更大的值，则不是幸运数。
- 若不存在更大值，则把 minVal 加入答案。
复杂度分析
设行数为 m、列数为 n。
时间复杂度：O(m * n + m * m)（每行一次行扫描 + 一次列扫描）。
空间复杂度：O(1)（不计输出）。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public List<Integer> luckyNumbers (int[][] matrix) {
List<Integer> ans = new ArrayList<>();
int m = matrix.length, n = matrix[0].length;
for (int i = 0; i < m; i++) {
int minVal = matrix[i][0], col = 0;
for (int j = 1; j < n; j++) {
if (matrix[i][j] < minVal) {
minVal = matrix[i][j];
col = j;
}
}
boolean isColMax = true;
for (int r = 0; r < m; r++) {
if (matrix[r][col] > minVal) {
isColMax = false;
break;
}
}
if (isColMax) {
ans.add(minVal);
}
}
return ans;
}
}func luckyNumbers(matrix [][]int) []int {
m, n := len(matrix), len(matrix[0])
ans := []int{}
for i := 0; i < m; i++ {
minVal, col := matrix[i][0], 0
for j := 1; j < n; j++ {
if matrix[i][j] < minVal {
minVal = matrix[i][j]
col = j
}
}
isColMax := true
for r := 0; r < m; r++ {
if matrix[r][col] > minVal {
isColMax = false
break
}
}
if isColMax {
ans = append(ans, minVal)
}
}
return ans
}class Solution {
public:
vector<int> luckyNumbers (vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<int> ans;
for (int i = 0; i < m; ++i) {
int minVal = matrix[i][0], col = 0;
for (int j = 1; j < n; ++j) {
if (matrix[i][j] < minVal) {
minVal = matrix[i][j];
col = j;
}
}
bool isColMax = true;
for (int r = 0; r < m; ++r) {
if (matrix[r][col] > minVal) {
isColMax = false;
break;
}
}
if (isColMax) ans.push_back(minVal);
}
return ans;
}
};class Solution:
def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
m, n = len(matrix), len(matrix[0])
ans = []
for i in range(m):
min_val = matrix[i][0]
col = 0
for j in range(1, n):
if matrix[i][j] < min_val:
min_val = matrix[i][j]
col = j
is_col_max = True
for r in range(m):
if matrix[r][col] > min_val:
is_col_max = False
break
if is_col_max:
ans.append(min_val)
return ansvar luckyNumbers = function(matrix) {
const m = matrix.length;
const n = matrix[0].length;
const ans = [];
for (let i = 0; i < m; i++) {
let minVal = matrix[i][0];
let col = 0;
for (let j = 1; j < n; j++) {
if (matrix[i][j] < minVal) {
minVal = matrix[i][j];
col = j;
}
}
let isColMax = true;
for (let r = 0; r < m; r++) {
if (matrix[r][col] > minVal) {
isColMax = false;
break;
}
}
if (isColMax) ans.push(minVal);
}
return ans;
};
Comments