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.
1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5 public List<Integer> luckyNumbers (int[][] matrix) {
6 List<Integer> result = new ArrayList<>();
7 int[] rowMin = new int[matrix.length];
8
9 for (int i = 0; i < matrix.length; i++) {
10 int minIndex = 0;
11 for (int j = 1; j < matrix[i].length; j++) {
12 if (matrix[i][j] < matrix[i][minIndex]) {
13 minIndex = j;
14 }
15 }
16 rowMin[i] = minIndex;
17 }
18
19 for (int j = 0; j < matrix[0].length; j++) {
20 int max = matrix[0][j];
21 for (int i = 0; i < matrix.length; i++) {
22 max = Math.max(max, matrix[i][j]);
23 }
24 for (int i = 0; i < matrix.length; i++) {
25 if (matrix[i][j] == max && j == rowMin[i]) {
26 result.add(matrix[i][j]);
27 }
28 }
29 }
30 return result;
31 }
32}This Java implementation keeps track of the minimum row indices and checks for column maximums. The values that qualify as row minimum and column maximum are added to the result 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.
1using System.Collections.Generic;
using System.Linq;
public class Solution {
public IList<int> LuckyNumbersWithSet(int[][] matrix) {
HashSet<int> rowMinSet = new HashSet<int>();
foreach (var row in matrix) {
rowMinSet.Add(row.Min());
}
int[] colMax = new int[matrix[0].Length];
Array.Fill(colMax, int.MinValue);
for (int j = 0; j < matrix[0].Length; j++) {
for (int i = 0; i < matrix.Length; i++) {
colMax[j] = Math.Max(colMax[j], matrix[i][j]);
}
}
List<int> luckyNumbers = new List<int>();
foreach (int max in colMax) {
if (rowMinSet.Contains(max)) {
luckyNumbers.Add(max);
}
}
return luckyNumbers;
}
}Set operations enable efficiently tracking minima and maxima in C#. The solution checks intersection occurrences to derive lucky numbers.