Leetcode1380: lucky numbers in matrix

Catalog

1. Title Description

2. Problem solving analysis

Time complexity analysis

Spatial complexity analysis

3. Code implementation

4. Are there multiple lucky numbers ？

---

1. Title Description

         To give you one m * n Matrix , The number in the matrix Each are not identical . Please press arbitrarily Return all the lucky numbers in the matrix in order . Lucky number refers to the elements in the matrix that meet the following two conditions at the same time ：

1. The smallest of all elements in the same row
2. The largest of all elements in the same column

Example 1：
Input ：matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output ：[15]
explain ：15 Is the only lucky number , Because it is the smallest value in its row , It is also the maximum value in the column .

Example 2：
Input ：matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output ：[12]
explain ：12 Is the only lucky number , Because it is the smallest value in its row , It is also the maximum value in the column .

Example 3：
Input ：matrix = [[7,8],[1,2]]
Output ：[7]

Tips ：
m == mat.length
n == mat[i].length
1 <= n, m <= 50
1 <= matrix[i][j] <= 10^5
All elements in the matrix are different

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/lucky-numbers-in-a-matrix
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

2. Problem solving analysis

         Obviously , There is at most one lucky number in each line , At most, there is only one lucky number in each column .

         The intuitive method is progressive scanning . Find the minimum value in the first row , Then confirm whether it is the maximum value of the column , If yes, it is a lucky number . Column by column scanning is also acceptable , The reason is the same .      

Time complexity analysis

        Make m and n Represents the number of rows and columns of input data respectively .

        For each line , The time complexity to find the minimum value is , The time complexity of finding the maximum value in the column where the minimum value is located is , Therefore, the processing time complexity of each row is . All in all m That's ok , So the total time complexity is .

        therefore , If the number of rows is greater than the number of columns , It should be advantageous to scan by column .

Spatial complexity analysis

        During the search , In addition to storing a row minimum 、 The column where the row minimum value is located and the column maximum value , No additional storage required , So the space complexity is constant complexity .

3. Code implementation

class Solution:    
    def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
        m = len(matrix)    # number of row
        n = len(matrix[0]) # number of col
        rslt = []
        for k in range(m): # Iteration over each row           
            # Find row min and also the min index
            # rowmin,minidx = self.findMin(matrix[k])
            rowmin = matrix[k][0]
            rowminidx = 0
            for col in range(1,n):
                if matrix[k][col] < rowmin:
                    rowmin = matrix[k][col]
                    rowminidx = col

            # Find the max of column[minidx]
            colmax = matrix[0][rowminidx]
            for k in range(1,m):
                if matrix[k][rowminidx] > colmax:
                    colmax = matrix[k][rowminidx]
            # Whether the row-min coincidence with col-max
            if colmax == rowmin:            
                rslt.append(colmax)
        return rslt        

if __name__ == '__main__':        
    
    sln = Solution()

    matrix = [[3,7,8],[9,11,13],[15,16,17]]
    print(sln.luckyNumbers(matrix))          

    matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
    print(sln.luckyNumbers(matrix))                      
    
    matrix = [[7,8],[1,2]]
    print(sln.luckyNumbers(matrix))                          

    matrix = [[7]] # corner case
    print(sln.luckyNumbers(matrix))                          

    matrix = [[8,7],[1,9]]
    print(sln.luckyNumbers(matrix))  

         however , The above solution may be a little naive^-^. stay Leetcode The performance in submission is relatively poor ：

# ======================================================================
# Execution time ：96 ms, In all Python3 Defeated in submission 5.16% Users of
# Memory consumption ：32.4 MB, In all Python3 Defeated in submission 5.16% Users of        
# ======================================================================

        Further efforts are needed .

4. Are there multiple lucky numbers ？

         The Title Description implies that there may be multiple lucky numbers . But I want to design such a testcase When , It seems impossible to build such testcase Come on . I thought it over , It is believed that there should be no multiple lucky numbers that meet the requirements of this question .

         Prove the following ： Reduction to absurdity .

        It's not general , hypothesis A[0][0] A lucky number , be A[0][0] Is the minimum value of the first line , meanwhile A[0][0] Is the maximum value of the first column . Suppose there is another number A[i][j](i>0, j>0), It's also a lucky number , By definition ,A[i][j] For the first time (i+1) The minimum value of the row , So I must be satisfied A[i][j]<A[0][j]<A[0][0]<A[0][j], This is related to A[i][j] It's a lucky number （ Column maximum ） The conclusion of is contradictory . Therefore, there cannot be more than one lucky number .

        Based on this , The above program can be slightly optimized . That is, you can quit in advance after finding a lucky number .