Problem of The Day: Lucky Numbers in a Matrix

Problem Statement

Intuition

My first thought on solving this problem is to identify the smallest number in each row and the largest number in each column. The lucky number is one that is both the smallest in its row and the largest in its column.

Approach

1. Traverse each row of the matrix and find the minimum value in each row. Store these minimum values in a list.
2. Traverse each column of the matrix and find the maximum value in each column.
3. Check if any of the maximum values found in the columns are present in the list of minimum values from the rows. If they are, those values are the lucky numbers.
4. Return the list of lucky numbers.

Complexity

• Time complexity: The time complexity is (O(n \times m)), where (n) is the number of rows and (m) is the number of columns in the matrix. This is because we traverse each element of the matrix at least once.

• Space complexity: The space complexity is (O(n + m)), where (n) is the number of rows (for storing minimum values) and (m) is the number of columns (for storing maximum values).

Code

class Solution:
    def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
        min_vals = []
        res = []
        ROWS = len(matrix)
        COLS = len(matrix[0])

        # Find the minimum value in each row
        for row in matrix:
            min_vals.append(min(row))

        # Find the maximum value in each column and check if it's a lucky number
        for col in range(COLS):
            curr_max = float('-inf')
            for row in range(ROWS):
                curr_max = max(curr_max, matrix[row][col])
            if curr_max in min_vals:
                res.append(curr_max)

        return res

Editorial

Approach 1: Simulation

class Solution:
    def luckyNumbers(self, matrix):
        N = len(matrix)
        M = len(matrix[0])

        rowMin = []
        for i in range(N):
            rMin = float('inf')
            for j in range(M):
                rMin = min(rMin, matrix[i][j])
            rowMin.append(rMin)

        colMax = []
        for i in range(M):
            cMax = float('-inf')
            for j in range(N):
                cMax = max(cMax, matrix[j][i])
            colMax.append(cMax)

        luckyNumbers = []
        for i in range(N):
            for j in range(M):
                if matrix[i][j] == rowMin[i] and matrix[i][j] == colMax[j]:
                    luckyNumbers.append(matrix[i][j])

        return luckyNumbers

• time: O(m * n)
• space: O(m + n)

Approach 2: Greedy

class Solution:
    def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
        N, M = len(matrix), len(matrix[0])

        r_min_max = float('-inf')
        for i in range(N):
            r_min = min(matrix[i])
            r_min_max = max(r_min_max, r_min)

        c_max_min = float('inf')
        for i in range(M):
            c_max = max(matrix[j][i] for j in range(N))
            c_max_min = min(c_max_min, c_max)

        if r_min_max == c_max_min:
            return [r_min_max]
        else:
            return []

• time: O(m * n)
• space: O(1)