Finding the Lucky Numbers in a Matrix

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.

Hints:
Find out and save the minimum of each row and maximum of each column in two lists.
Then scan through the whole matrix to identify the elements that satisfy the criteria.

Minimum of Each Row and Maximum of Each Columns

We store the minimum of each row and the maximum of the each column in two lists (which result in O(M+N) space requirement). Iterating the matrix and update these two lists.

Iterate again and the lucky numbers are those where the two lists intersect. The overall complexity is O(MN).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    vector<int> luckyNumbers (vector<vector<int>>& matrix) {
        vector<int> res;        
        int R = matrix.size();
        if (R == 0) return {};
        int C = matrix[0].size();
        vector<int> rowMin(R, INT_MAX);
        vector<int> colMax(C, -INT_MAX-1);
        for (int r = 0; r < R; ++ r) {
            for (int c = 0; c < C; ++ c) {
                rowMin[r] = min(rowMin[r], matrix[r][c]);
                colMax[c] = max(colMax[c], matrix[r][c]);
            }
        }
        for (int r = 0; r < R; ++ r) {
            for (int c = 0; c < C; ++ c) {
                if (rowMin[r] == colMax[c]) {
                    res.push_back(matrix[r][c]);
                }
            }
        }
        return res;
    }
};

class Solution {
public:
    vector<int> luckyNumbers (vector<vector<int>>& matrix) {
        vector<int> res;        
        int R = matrix.size();
        if (R == 0) return {};
        int C = matrix[0].size();
        vector<int> rowMin(R, INT_MAX);
        vector<int> colMax(C, -INT_MAX-1);
        for (int r = 0; r < R; ++ r) {
            for (int c = 0; c < C; ++ c) {
                rowMin[r] = min(rowMin[r], matrix[r][c]);
                colMax[c] = max(colMax[c], matrix[r][c]);
            }
        }
        for (int r = 0; r < R; ++ r) {
            for (int c = 0; c < C; ++ c) {
                if (rowMin[r] == colMax[c]) {
                    res.push_back(matrix[r][c]);
                }
            }
        }
        return res;
    }
};

In Python, we can use the zip function and the asterisk operator to unpack the matrix and thus transpose the matrix that allow us to retreive the columns of the matrix. Then we can compute the intersections of both lists (as sets).

1
2
3
4

class Solution:
    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
        return list({min(row) for row in matrix} & \
                    {max(col) for col in zip(*matrix)});

class Solution:
    def luckyNumbers (self, matrix: List[List[int]]) -> List[int]:
        return list({min(row) for row in matrix} & \
                    {max(col) for col in zip(*matrix)});

As you can see, the Python one-liner solution is very elegant and powerful.

–EOF (The Ultimate Computing & Technology Blog) —