Finding the Lucky Numbers in a Matrix

  • Time:2020-09-10 13:03:17
  • Class:Weblog
  • Read:31

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) —

Recommend:
Dina Boluarte sworn in as Peru's new president, calls for "
PAP special operations soldiers in field training
Commentary: Why Belt and Road cooperation matters to stronger Ch
Senior Guangdong provincial legislator under probe
EU new sanctions target Russia's armed forces, drone supply
Rice noodle makers whiff success in export business
China's forex reserves rise in November
Consumer sentiment weakens in eurozone: ECB
Suicide bombing hits Indonesia's police station, killing 2, inju
China's foreign trade expands steadily in first 11 months
Share:Facebook Twitter
Comment list
Comment add