Formatted question description: https://leetcode.ca/all/1380.html
1380. Lucky Numbers in a Matrix
Level
Easy
Description
Given a m * n
matrix of distinct numbers, return all lucky numbers in the matrix in any order.
A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.
Example 1:
Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column
Example 2:
Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output: [12]
Explanation: 12 is the only lucky number since it is the minimum in its row and the maximum in its column.
Example 3:
Input: matrix = [[7,8],[1,2]]
Output: [7]
Constraints:
m == mat.length
n == mat[i].length
1 <= n, m <= 50
1 <= matrix[i][j] <= 10^5
.- All elements in the matrix are distinct.
Algorithm
At the beginning, I thought of a brute force solution, searching whether each number meets such a limit, but found that this should be m^2 * n^2
time complexity, because it needs to traverse each element and traverse the current row and column at the same time.
But based on observations, we only need the minimum value of each row and the maximum value of each column, so that we can find one of them first and then look at the intersection. If it exists, it meets this requirement. This only needs to traverse each element of the matrix once.
Code
Java
-
public class Lucky_Numbers_in_a_Matrix { // time:O(mn) space:O(m) // set intersection public List<Integer> luckyNumbers(int[][] matrix) { if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return new ArrayList<>(); HashSet<Integer> minOfRows = new HashSet<>(); for (int[] row : matrix) { int min = row[0]; for (int n : row) { min = Math.min(min, n); } minOfRows.add(min); } int m = matrix.length; int n = matrix[0].length; List<Integer> res = new ArrayList<>(); for (int j = 0; j < n; j++) { int max = matrix[0][j]; for (int i = 0; i < m; i++) { max = Math.max(max, matrix[i][j]); } // intersection check if (minOfRows.contains(max)) res.add(max); } return res; } }
-
// OJ: https://leetcode.com/problems/lucky-numbers-in-a-matrix // Time: O(MN) // Space: O(M + N) class Solution { public: vector<int> luckyNumbers (vector<vector<int>>& A) { int M = A.size(), N = A[0].size(); vector<int> row(M, INT_MAX), col(N, INT_MIN); for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { row[i] = min(row[i], A[i][j]); } } for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { col[i] = max(col[i], A[j][i]); } } vector<int> ans; for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { if (A[i][j] == row[i] && A[i][j] == col[j]) ans.push_back(A[i][j]); } } return ans; } };
-
print("Todo!")
Or, first, obtain the minimum value of each row and the column of the minimum values. Then, for each minimum value, check whether it is the maximum value in its column. If so, add it to the result list. Finally, return the result list.
Java
-
class Solution { public List<Integer> luckyNumbers (int[][] matrix) { int rows = matrix.length, columns = matrix[0].length; int[] mins = new int[rows]; for (int i = 0; i < rows; i++) { int min = matrix[i][0]; int minColumn = 0; for (int j = 1; j < columns; j++) { if (matrix[i][j] < min) { min = matrix[i][j]; minColumn = j; } } mins[i] = minColumn; } List<Integer> luckyNumbers = new ArrayList<Integer>(); for (int i = 0; i < rows; i++) { int minColumn = mins[i]; int min = matrix[i][minColumn]; boolean flag = true; for (int j = 0; j < rows; j++) { if (j == i) continue; else if (matrix[j][minColumn] > min) { flag = false; break; } } if (flag) luckyNumbers.add(min); } return luckyNumbers; } }
-
// OJ: https://leetcode.com/problems/lucky-numbers-in-a-matrix // Time: O(MN) // Space: O(M + N) class Solution { public: vector<int> luckyNumbers (vector<vector<int>>& A) { int M = A.size(), N = A[0].size(); vector<int> row(M, INT_MAX), col(N, INT_MIN); for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { row[i] = min(row[i], A[i][j]); } } for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { col[i] = max(col[i], A[j][i]); } } vector<int> ans; for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { if (A[i][j] == row[i] && A[i][j] == col[j]) ans.push_back(A[i][j]); } } return ans; } };
-
print("Todo!")