#1380

Easy

LeetCode Problem Workspace

Lucky Numbers in a Matrix

The Lucky Numbers in a Matrix problem involves finding elements that are the minimum in their row and maximum in their column.

array matrix

Problem Statement

You are given a matrix of distinct integers with dimensions m x n. Your task is to identify all lucky numbers in the matrix. A lucky number is defined as an element that is the minimum in its row and the maximum in its column.

For example, in the matrix [[3,7,8], [9,11,13], [15,16,17]], the number 15 is the lucky number because it is the minimum in its row and the maximum in its column.

Examples

Example 1

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]

Output: [15]

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]

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]

7 is the only lucky number since it is the minimum in its row and the maximum in its column.

Constraints

m == mat.length
n == mat[i].length
1 <= n, m <= 50
1 <= matrix[i][j] <= 105.
All elements in the matrix are distinct.

Solution Approach

Row Minimums

First, find the minimum element in each row and store these values. These candidates will be checked against the column maximums to determine if they are lucky numbers.

Column Maximums

Next, find the maximum element in each column. These values will help verify whether the row minimum is the largest element in its respective column.

Verification

For each candidate from the row minimums, check if it also satisfies the column maximum condition. If it does, it is a lucky number.

Complexity Analysis

Metric	Value
Time	O(N * M)
Space	O(1)

The time complexity of this solution is O(N * M), where N and M are the dimensions of the matrix. This is because we need to scan each row and column at least once. The space complexity is O(1) as we are only storing a few lists for row minimums and column maximums.

What Interviewers Usually Probe

The candidate can efficiently identify the row minimums and column maximums.
They correctly validate the lucky number condition for each element.
They optimize the solution by ensuring minimal space usage.

Common Pitfalls or Variants

Common pitfalls

Failing to identify the correct row minimums or column maximums, leading to incorrect results.
Not properly validating that a row minimum is also the column maximum.
Using excessive space by storing unnecessary intermediate data or using complex data structures.

Follow-up variants

What if the matrix has non-distinct values? How would the solution change?
Can the matrix contain negative numbers? If so, how does it affect the solution?
What if we have to find lucky numbers for submatrices instead of the entire matrix?

FAQ

What is the primary approach to solving the Lucky Numbers in a Matrix problem?

The primary approach involves finding the minimum values of each row and the maximum values of each column, then verifying if a number is both.

How do I ensure I find the correct lucky numbers in the matrix?

Ensure that the number is the minimum in its row and the maximum in its column. This is the key property for a lucky number.

What happens if multiple lucky numbers exist in the matrix?

The problem requires returning all lucky numbers, so simply collect and return all valid numbers that satisfy the lucky number condition.

Does the matrix size affect the complexity of the solution?

Yes, the time complexity is O(N * M) where N is the number of rows and M is the number of columns. Larger matrices will increase the time required to solve the problem.

Can I use extra space to solve this problem?

While the space complexity is O(1), you can use extra space for storing row minimums and column maximums temporarily. However, it's important to optimize space usage where possible.

terminal

Solution

Solution 1: Maintain Row Minimum and Column Maximum

We can use two arrays $rows$ and $cols$ to record the minimum value of each row and the maximum value of each column in the matrix. Then, we traverse each element in the matrix, checking whether this element is the minimum value of its row and the maximum value of its column. If it is, then this element is a lucky number, and we add it to the answer array.

1

2

3

4

5

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

Continue Practicing

#1391 check if there is a valid path in a grid #1368 minimum cost to make at least one valid path in a grid #1351 count negative numbers in a sorted matrix