1380. Lucky Numbers in a Matrix


Problem Description

The problem provides us with a matrix of distinct numbers that is m rows by n columns in size. We are asked to identify all the "lucky numbers" in this matrix. A lucky number is defined as one that is the smallest number in its row and also the largest number in its column. The challenge is to return a list of these lucky numbers in any order.

To approach this problem, we need to iterate through each element in the matrix to compare it with other elements in the same row and column. The uniqueness of each number simplifies the task since there will be no duplicates to consider.

Intuition

The intuition behind the proposed solution is to optimize the search for lucky numbers by avoiding unnecessary comparisons. Here's the thought process:

  • For each row in the matrix, we find the smallest element since a lucky number must be the minimum in its row.
  • Similarly, we determine the largest element for each column, as a lucky number must also be the maximum in its column.

With these two lists of minimum row values and maximum column values, we can find the intersection set that contains elements that are both the minimum in their row and the maximum in their column. These are our "lucky numbers."

The implementation uses Python's list comprehensions and set intersection to achieve this efficiently:

  • To find the row minimums, we generate a set by iterating through each row and apply the min function.
  • To find the column maximums, we generate another set by transposing the matrix with zip(*matrix) and again use the max function for each column.
  • Finally, by intersecting these two sets, we get the lucky numbers.

The solution assumes that the rows and columns property of the matrix object are the minimum and maximum functions applied as shown in the solution.

Solution Approach

The solution uses Python list comprehensions and the min and max functions to create two sets, one containing the minimum element of each row and the other containing the maximum element of each column. These two sets are then intersected to find the lucky numbers.

Here's how the code works:

  1. rows = min(row for row in matrix) – This line iterates over each row in the matrix and finds the smallest element in that row. The min function applies within the comprehension to each row. This results in a set of minimum values, one for each row.

  2. cols = max(col for col in zip(*matrix)) – This line transposes the matrix using zip(*matrix), which groups elements from each row into columns. By iterating over this transposed matrix, the code finds the maximum element in each of the original columns. This creates a set of the maximum column values.

  3. return list(rows & cols) – Finally, the intersection (&) of the two sets is determined, which gives us the lucky numbers. Since a lucky number is defined as being both the minimum in its row and maximum in its column, intersection checks which values are present in both sets. Only those that meet both criteria will be in the result. The intersection is then converted back to a list before being returned.

The algorithm is efficient because it takes linear time with respect to the elements in the matrix (O(mn), where m is the number of rows and n is the number of columns). This is far more efficient than a brute force approach that would require a comparison of each element with every other element in its row and column.

The use of sets for storing the minimum row values and maximum column values is a crucial part of the approach because it allows for the interception operation to be performed swiftly.

Note: The solution given seems to assume that rows and cols would be sets. However, the current implementation with list comprehensions actually creates lists. To get the correct result, the implementation would need to be corrected to use the set of minimum row values and the set of maximum column values before the intersection. The implementation as stated would cause a TypeError because Python lists do not support intersection. Here's the corrected implementation:

1class Solution:
2    def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
3        rows = {min(row) for row in matrix}  # Use a set comprehension
4        cols = {max(col) for col in zip(*matrix)}  # Use a set comprehension
5        return list(rows & cols)

With this adjustment, the solution should work correctly, finding the lucky numbers in the matrix.

Example Walkthrough

Let's go through a small example to illustrate the solution approach. Consider the following matrix:

378
91113
151617

According to the problem description, we need to find the numbers that are the smallest in their row and the largest in their column.

First, we find the smallest number in each row:

  • For the first row, the smallest number is 3.
  • For the second row, the smallest number is 9.
  • For the third row, the smallest number is 15.

Now, we have the set of minimum row values: {3, 9, 15}.

Next, we find the largest number in each column by transposing the matrix:

  • The transposed columns become [3, 9, 15], [7, 11, 16], and [8, 13, 17].
  • The largest number in the first transposed column is 15.
  • The largest number in the second transposed column is 16.
  • The largest number in the third transposed column is 17.

From this, we get the set of maximum column values: {15, 16, 17}.

The final step is to find the intersection of these two sets:

  • Our minimum row values set is {3, 9, 15}.
  • Our maximum column values set is {15, 16, 17}.
  • The intersection of these two sets is {15}.

Therefore, the lucky number in this matrix is 15 because it is the only number that satisfies both criteria, and our final result is [15].

Python Solution

1class Solution:
2    def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
3        # Find the minimum element in each row and store as a set
4        min_in_rows = {min(row) for row in matrix}
5      
6        # Transpose the matrix to work with columns as rows and find the maximum
7        # element in each original column, also store as a set
8        max_in_columns = {max(col) for col in zip(*matrix)}
9      
10        # Find the intersection (common elements) between the sets of minimum elements in rows and
11        # the maximum elements in columns, which represents the "lucky numbers"
12        lucky_numbers = list(min_in_rows & max_in_columns)
13      
14        # Return the list of lucky numbers
15        return lucky_numbers
16

Java Solution

1import java.util.ArrayList;
2import java.util.List;
3import java.util.Arrays;
4
5class Solution {
6  
7    // Method to find all lucky numbers in the matrix.
8    // A lucky number is defined as a number which is the minimum of its row and maximum of its column.
9    public List<Integer> luckyNumbers(int[][] matrix) {
10      
11        // m represents the number of rows
12        // n represents the number of columns
13        int m = matrix.length, n = matrix[0].length;
14
15        // 'minInRows' will hold the minimum values for each row
16        // 'maxInCols' will hold the maximum values for each column
17        int[] minInRows = new int[m];
18        int[] maxInCols = new int[n];
19
20        // Initialize 'minInRows' with a maximum valid integer value
21        Arrays.fill(minInRows, Integer.MAX_VALUE);
22
23        // Nested loops to calculate minInRows and maxInCols
24        for (int i = 0; i < m; i++) {
25            for (int j = 0; j < n; j++) {
26                // Update the minimum value in the current row
27                minInRows[i] = Math.min(minInRows[i], matrix[i][j]);
28                // Update the maximum value in the current column
29                maxInCols[j] = Math.max(maxInCols[j], matrix[i][j]);
30            }
31        }
32
33        // List to store all the lucky numbers found
34        List<Integer> luckyNumbers = new ArrayList<>();
35
36        // Nested loops to find common elements in 'minInRows' and 'maxInCols'
37        for (int i = 0; i < m; i++) {
38            for (int j = 0; j < n; j++) {
39                // Check if the current number is a lucky number
40                if (minInRows[i] == maxInCols[j]) {
41                    // Add the number to the list of lucky numbers
42                    luckyNumbers.add(minInRows[i]);
43                }
44            }
45        }
46
47        // Return the list of lucky numbers
48        return luckyNumbers;
49    }
50}
51

C++ Solution

1#include <vector>
2#include <algorithm>
3#include <cstring>
4
5class Solution {
6public:
7    std::vector<int> luckyNumbers (std::vector<std::vector<int>>& matrix) {
8        int numRows = matrix.size(); // Number of rows in the matrix
9        int numCols = matrix[0].size(); // Number of columns in the matrix
10        std::vector<int> minInRows(numRows, INT_MAX); // Initialize vector to store min values for every row
11        std::vector<int> maxInCols(numCols, INT_MIN); // Initialize vector to store max values for every column
12      
13        // Find the minimum value in each row and the maximum value in each column
14        for(int i = 0; i < numRows; ++i) {
15            for(int j = 0; j < numCols; ++j) {
16                // Update the min for the ith row if the current element is less than the stored min
17                minInRows[i] = std::min(minInRows[i], matrix[i][j]);
18                // Update the max for the jth column if the current element is greater than the stored max
19                maxInCols[j] = std::max(maxInCols[j], matrix[i][j]);
20            }
21        }
22      
23        std::vector<int> luckyNumbers; // Vector to store the lucky numbers
24        // Check for lucky numbers - values that are the minimum in their rows and maximum in their columns
25        for(int i = 0; i < numRows; ++i) {
26            for(int j = 0; j < numCols; ++j) {
27                // If the number is equal to the min of its row and the max of its column, it's a lucky number
28                if(matrix[i][j] == minInRows[i] && matrix[i][j] == maxInCols[j]) {
29                    luckyNumbers.push_back(matrix[i][j]);
30                }
31            }
32        }
33      
34        return luckyNumbers; // Return the list of lucky numbers
35    }
36};
37

Typescript Solution

1function luckyNumbers(matrix: number[][]): number[] {
2    // Get the number of rows (m) and columns (n) from the matrix.
3    const numRows = matrix.length;
4    const numCols = matrix[0].length;
5
6    // Initialize arrays to store the minimum values of each row and the maximum values of each column.
7    const minRowValues: number[] = new Array(numRows).fill(Infinity);
8    const maxColValues: number[] = new Array(numCols).fill(0);
9
10    // Find the minimum and maximum values for rows and columns, respectively.
11    for (let row = 0; row < numRows; ++row) {
12        for (let col = 0; col < numCols; col++) {
13            minRowValues[row] = Math.min(minRowValues[row], matrix[row][col]);
14            maxColValues[col] = Math.max(maxColValues[col], matrix[row][col]);
15        }
16    }
17
18    // Initialize array to store the lucky numbers.
19    const luckyNumbers: number[] = [];
20
21    // Check each element in the minimum row values against the maximum column values.
22    // If any value is both the minimum in its row and the maximum in its column, it's considered lucky.
23    for (let row = 0; row < numRows; ++row) {
24        for (let col = 0; col < numCols; col++) {
25            if (minRowValues[row] === maxColValues[col]) {
26                luckyNumbers.push(minRowValues[row]);
27            }
28        }
29    }
30
31    // Return the array of lucky numbers found in the matrix.
32    return luckyNumbers;
33}
34

Time and Space Complexity

Time Complexity

The luckyNumbers method consists of several operations. Let's analyze them step by step:

  1. min(row for row in matrix): This operation computes the minimum of each row in the matrix. Since it examines each element of the row to find the minimum, this operation takes O(n) time for each row, where n is the number of columns. Since there are m rows in the matrix, the total time taken for this step is O(m * n).

  2. max(col for col in zip(*matrix)): This operation first transposes the matrix using zip(*matrix), which is O(1) since it returns an iterator. Then, it computes the maximum for each column (originally row in the transposed matrix). Computing the maximum for one column takes O(m), and since there are n columns, the total time for this step is O(m * n).

  3. list(rows & cols): The intersection operation & between two sets happens in O(min(len(rows), len(cols))) time in the average case. Since rows is a set with at most m elements (one for each row) and cols is a set with at most n elements (one for each column), this step will take O(min(m, n)) time.

Combining these steps, the dominant term is the one with O(m * n), as this is the largest factor in the time complexity.

Therefore, the overall time complexity is O(m * n).

Space Complexity

Now let's look at the space complexity:

  1. rows: Stores the minimum element of each row, so it has at most m elements.
  2. cols: Stores the maximum element of each column, so it has at most n elements.

The space taken by the rows and cols sets is O(m) and O(n) respectively. There is no additional significant space usage.

Hence, the total space complexity is O(m + n), as we need to store the minimum and the maximum elements of the rows and columns separately.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫