Problem Description

You are given an m x n matrix containing distinct numbers. Your task is to find all the lucky numbers in this matrix.

A lucky number is defined as an element that satisfies both of these conditions:

• It is the smallest number in its row
• It is the largest number in its column

For example, consider this matrix:

[3, 7, 8]
[9, 11, 13]
[15, 16, 17]

The number 15 is a lucky number because:

• It's the minimum in its row: min(15, 16, 17) = 15
• It's the maximum in its column: max(3, 9, 15) = 15

The solution works by:

1. Finding the minimum value in each row and storing them in a set rows
2. Finding the maximum value in each column and storing them in a set cols
3. Finding the intersection of these two sets - any number that appears in both sets must be both a row minimum and a column maximum

The code zip(*matrix) transposes the matrix to easily access columns, allowing us to find the maximum of each column. The intersection operation rows & cols finds elements that are both row minimums and column maximums, which are exactly the lucky numbers we're looking for.

You need to return all such lucky numbers in any order. Note that there might be zero, one, or multiple lucky numbers in a given matrix.

Intuition

The key insight comes from understanding what makes a number "lucky" - it must be simultaneously the smallest in its row and the largest in its column. This dual constraint creates a unique property: if a number satisfies both conditions, it must be special.

Think about it this way: if a number is the minimum in its row, we can collect all such row minimums. Similarly, if a number is the maximum in its column, we can collect all such column maximums. Now here's the clever part - a lucky number must appear in both collections.

Why? Because a lucky number needs to satisfy both conditions at the same time. If we have the number 15 that is the minimum of its row, it goes into our row minimums collection. If that same 15 is also the maximum of its column, it goes into our column maximums collection. The only way a number can appear in both collections is if it's both a row minimum AND a column maximum - which is exactly our definition of a lucky number.

This leads us to a simple approach: instead of checking each element against all elements in its row and column (which would be inefficient), we can:

1. Pre-compute all row minimums
2. Pre-compute all column maximums
3. Find which numbers appear in both sets

The intersection of these two sets gives us all the lucky numbers, because only lucky numbers can be present in both sets. This transforms a potentially complex nested loop problem into a clean set operation problem.

Solution Approach

We implement the solution using two sets to maintain row minimums and column maximums, then find their intersection.

Step 1: Find Row Minimums

We iterate through each row in the matrix and find the minimum value in that row using the min() function. We store all these minimums in a set called rows:

rows = {min(row) for row in matrix}

This set comprehension processes each row and keeps only the minimum values.

Step 2: Find Column Maximums

To find the maximum in each column, we need to transpose the matrix first. The expression zip(*matrix) achieves this:

• The * operator unpacks the matrix rows
• zip() then groups elements by their column position

For example, if matrix is [[1,2], [3,4]], then zip(*matrix) gives us [(1,3), (2,4)] - each tuple represents a column.

We then find the maximum of each column:

cols = {max(col) for col in zip(*matrix)}

Step 3: Find Intersection

The lucky numbers are exactly those that appear in both sets. We use the set intersection operator & to find common elements:

return list(rows & cols)

Why This Works:

• If a number x is in the rows set, it means x is the minimum of some row
• If the same x is in the cols set, it means x is the maximum of some column
• When x appears in both sets, it satisfies both conditions for being a lucky number

Time Complexity: O(m × n) where m is the number of rows and n is the number of columns, as we need to traverse the entire matrix.

Space Complexity: O(m + n) for storing at most m row minimums and n column maximums.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this 3×3 matrix:

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

Step 1: Find Row Minimums

We examine each row and find its minimum value:

• Row 0: [3, 7, 8] → minimum is 3
• Row 1: [9, 11, 13] → minimum is 9
• Row 2: [15, 16, 17] → minimum is 15

So our set of row minimums is: rows = {3, 9, 15}

Step 2: Find Column Maximums

First, we transpose the matrix using zip(*matrix):

• Column 0: [3, 9, 15]
• Column 1: [7, 11, 16]
• Column 2: [8, 13, 17]

Now we find the maximum of each column:

• Column 0: [3, 9, 15] → maximum is 15
• Column 1: [7, 11, 16] → maximum is 16
• Column 2: [8, 13, 17] → maximum is 17

So our set of column maximums is: cols = {15, 16, 17}

Step 3: Find Intersection

We need to find numbers that appear in both sets:

• rows = {3, 9, 15}
• cols = {15, 16, 17}
• rows & cols = {15}

The only number that appears in both sets is 15.

Verification: Let's verify that 15 is indeed a lucky number:

• Is 15 the minimum in its row? Yes, min(15, 16, 17) = 15 ✓
• Is 15 the maximum in its column? Yes, max(3, 9, 15) = 15 ✓

Therefore, [15] is our answer - the list containing the single lucky number in this matrix.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

The algorithm consists of three main operations:

1. Finding the minimum of each row: This requires iterating through all m rows, and for each row, examining all n elements. This takes O(m × n) time.
2. Finding the maximum of each column: The zip(*matrix) operation transposes the matrix, which internally iterates through all elements once, taking O(m × n) time. Then finding the maximum of each of the n columns requires examining all m elements per column, which is also O(m × n) time.
3. Finding the intersection of two sets: This operation takes O(min(m, n)) time, which is bounded by O(m × n).

Therefore, the overall time complexity is O(m × n) + O(m × n) + O(min(m, n)) = O(m × n).

Space Complexity: O(m + n)

The algorithm uses additional space for:

1. The rows set: Stores at most m elements (one minimum value per row), requiring O(m) space.
2. The cols set: Stores at most n elements (one maximum value per column), requiring O(n) space.
3. The zip(*matrix) operation creates an iterator that generates tuples on-the-fly, but the intermediate column tuples exist temporarily in memory during max computation, which uses O(m) space per column (but processed one at a time).
4. The final list from the intersection: Contains at most min(m, n) elements, which is bounded by O(m + n).

The dominant space usage comes from storing the row minimums and column maximums, giving us a total space complexity of O(m + n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Assuming There's Always Exactly One Lucky Number

A common misconception is that every matrix will have exactly one lucky number. In reality, a matrix can have:

• Zero lucky numbers: When no element satisfies both conditions
• Multiple lucky numbers: Though rare with distinct numbers, it's theoretically possible

Example of zero lucky numbers:

matrix = [[1, 10, 4, 2],
          [9, 3, 8, 7],
          [15, 16, 17, 12]]

# Row minimums: {1, 3, 12}
# Column maximums: {15, 16, 17, 12}
# Intersection: {12} - but wait, let's verify:
# 12 is NOT the min in its row [15, 16, 17, 12], min is 12 ✓
# 12 is the max in column 3: [2, 7, 12] ✓
# So there is one lucky number here

Better example with no lucky numbers:

matrix = [[7, 8],
          [1, 2]]

# Row minimums: {7, 1}
# Column maximums: {7, 8}
# Intersection: {7}
# But 7 is in position [0,0], and max of column 0 is 7 ✓, min of row 0 is 7 ✓
# So this has one lucky number

Actual example with no lucky numbers:

matrix = [[3, 6],
          [7, 2]]

# Row minimums: {3, 2}
# Column maximums: {7, 6}
# Intersection: {} - empty!
# No lucky numbers exist

2. Forgetting That Numbers Must Be Distinct

The problem states numbers are distinct, which simplifies the logic. If numbers weren't distinct, you'd need to handle duplicates carefully:

# If duplicates were allowed (hypothetical):
matrix = [[5, 5],
          [5, 5]]

# Every 5 would be both min of its row AND max of its column
# Would need to track positions, not just values

3. Inefficient Column Access Without Transposition

Without using zip(*matrix), developers might write inefficient code:

Inefficient approach:

# DON'T DO THIS - inefficient column access
column_maximums = set()
for j in range(len(matrix[0])):
    col_max = matrix[0][j]
    for i in range(1, len(matrix)):
        col_max = max(col_max, matrix[i][j])
    column_maximums.add(col_max)

Better approach (as in solution):

# DO THIS - elegant transposition
column_maximums = {max(col) for col in zip(*matrix)}

4. Returning Sets Instead of Lists

The problem asks for a list return type, but the intersection operation produces a set:

Wrong:

def luckyNumbers(self, matrix):
    rows = {min(row) for row in matrix}
    cols = {max(col) for col in zip(*matrix)}
    return rows & cols  # Returns a set, not a list!

Correct:

def luckyNumbers(self, matrix):
    rows = {min(row) for row in matrix}
    cols = {max(col) for col in zip(*matrix)}
    return list(rows & cols)  # Converts set to list

5. Memory Issues with Large Matrices

While the current solution is optimal, for extremely large matrices, you might want to find lucky numbers without storing all minimums/maximums:

Memory-optimized alternative:

def luckyNumbers(self, matrix):
    m, n = len(matrix), len(matrix[0])
    result = []
  
    for i in range(m):
        # Find minimum in row i and its column index
        row_min = min(matrix[i])
        min_col = matrix[i].index(row_min)
      
        # Check if this minimum is also the maximum in its column
        is_col_max = all(matrix[row][min_col] <= row_min for row in range(m))
      
        if is_col_max:
            result.append(row_min)
  
    return result

This approach trades time complexity for space efficiency when needed.