Sponsored
Sponsored
This approach involves two main steps. First, find the minimum element in each row and keep track of the potential lucky numbers. Then, verify these potential numbers to check if they are the maximum in their respective columns.
Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the matrix.
Space Complexity: O(m) for storing the minimum indices for each row.
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5public class Solution {
6 public IList<int> LuckyNumbers (int[][] matrix) {
7 List<int> result = new List<int>();
8 int m = matrix.Length;
9 int n = matrix[0].Length;
10 int[] minRow = new int[m];
11
12 for (int i = 0; i < m; i++) {
13 minRow[i] = int.MaxValue;
14 for (int j = 0; j < n; j++) {
15 minRow[i] = Math.Min(minRow[i], matrix[i][j]);
16 }
17 }
18
19 for (int j = 0; j < n; j++) {
20 int maxCol = int.MinValue;
21 for (int i = 0; i < m; i++) {
22 maxCol = Math.Max(maxCol, matrix[i][j]);
23 }
24 for (int i = 0; i < m; i++) {
25 if (matrix[i][j] == maxCol && matrix[i][j] == minRow[i]) {
26 result.Add(matrix[i][j]);
27 }
28 }
29 }
30 return result;
31 }
32}This C# method uses two nested loops to calculate row minima and column maxima. If there are matching values, they are appended to the results list.
This approach leverages set operations from mathematics to identify potential lucky numbers. We extract the row minimums and column maximums into separate sets and find the intersection of these sets for possible lucky numbers.
Time Complexity: O(m * n) where m is the number of rows and n is the number of columns.
Space Complexity: O(n) for storing column maximums.
1#include <unordered_set>
std::vector<int> luckyNumbersWithSet(std::vector<std::vector<int>>& matrix) {
std::unordered_set<int> minElements;
for (const auto& row : matrix) {
minElements.insert(*std::min_element(row.begin(), row.end()));
}
std::vector<int> maxCol(matrix[0].size(), 0);
for (int j = 0; j < matrix[0].size(); ++j) {
for (int i = 0; i < matrix.size(); ++i) {
maxCol[j] = std::max(maxCol[j], matrix[i][j]);
}
}
std::vector<int> luckyNumbers;
for (int j : maxCol) {
if (minElements.find(j) != minElements.end()) {
luckyNumbers.push_back(j);
}
}
return luckyNumbers;
}This solution uses C++ sets to keep track of row minimums and then checks against maximum columns to find the set intersection, representing the lucky numbers.