Finding the Lucky Numbers in a Matrix

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

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:
Switching to a Blogging Career: Can You Afford to Work from Home
4 Features that Will Enhance Your Blog
Amazon Surpasses Google: Should you Change your SEO Strategies?
How to Optimize WordPress Categories and Tags
Blogging Royalties: Michelle Obama Interviewing Barack on her Po
Content Marketing: Expectations Vs Reality
Blogger Skills: LinkedIn and Microsoft’s Digital Skill Programs
5 Tips for Creating a Content Strategy for Your eCommerce Websit
5 Tips You Can Use to Launch a Successful Property Management Bl
Blogging and Gaming Finally Recognized as Professions
Share:Facebook Twitter
Comment list
Comment add