Lucky Numbers in a Matrix: Row Min Meets Column Max

You are given an m x n matrix of distinct integers. Return all lucky numbers in the matrix in any order. A lucky number is an element that is the minimum element in its row and the maximum element in its column.

This is LeetCode 1380: Lucky Numbers in a Matrix, and it is one of the cleanest matrix problems for building intuition about row and column properties. The technique it teaches, scanning rows and columns independently then checking for overlap, appears in many matrix problems.

Why this problem matters

Matrix problems often require you to think about rows and columns as separate dimensions. Lucky Numbers in a Matrix trains exactly that skill. You need to identify a property along one axis (minimum in a row), a property along another axis (maximum in a column), and then find where those two properties intersect.

This "compute along one axis, check against another" pattern shows up in problems like Set Matrix Zeroes, where you track which rows and columns need zeroing, and in problems that ask you to find saddle points in numerical grids. Mastering the simple version here makes the harder variants feel familiar.

The key insight

There can be at most one lucky number in a matrix of distinct values. Why? Suppose value a is the minimum of row i and the maximum of column j. If another value b were also lucky (minimum of row k, maximum of column l), you can show a contradiction by comparing elements at the intersections of these rows and columns. The distinctness constraint means two such values cannot coexist.

This means your algorithm only needs to find at most one match. The approach is simple:

1. For each row, find the minimum value.
2. For each column, find the maximum value.
3. Any value that appears in both sets is a lucky number.

Since the values are distinct, you can use a set intersection to find matches in constant time per lookup.

The solution

def lucky_numbers(matrix: list[list[int]]) -> list[int]:
    row_mins = {min(row) for row in matrix}
    col_maxes = {max(col) for col in zip(*matrix)}
    return list(row_mins & col_maxes)

Let's walk through what each piece does.

The first line computes the minimum value for every row and stores them in a set. For the example matrix [[3,7,8],[9,11,13],[15,16,17]], this gives {3, 9, 15}.

The second line uses zip(*matrix) to transpose the matrix, turning columns into tuples, then finds the maximum of each column. For our example, the columns are (3,9,15), (7,11,16), and (8,13,17), giving column maxes {15, 16, 17}.

The third line takes the set intersection. The only value in both {3, 9, 15} and {15, 16, 17} is 15, so the answer is [15].

The zip(*matrix) trick is worth memorizing. It transposes any 2D list, which makes column operations as easy as row operations. You will use this pattern any time you need to iterate over columns in Python.

Visual walkthrough

Let's trace through the algorithm step by step. Watch how we first identify row minimums, then column maximums, then check for overlap.

The value 15 is the only one that satisfies both conditions. It is the smallest value in row 2, and it is also the largest value in column 0. That makes it the lucky number.

Complexity analysis

Time is O(m * n) where m is the number of rows and n is the number of columns. Finding the minimum of each row takes O(n) per row, for O(m * n) total. Finding the maximum of each column takes O(m) per column, for O(m * n) total. The set intersection is O(min(m, n)). Overall: O(m * n).

Space is O(m + n). The row minimums set holds at most m values, and the column maximums set holds at most n values. No additional data structures scale with m * n.

The building blocks

1. Row-wise aggregation

The pattern of computing a summary value for each row in a matrix:

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

This is the most common way to reduce a 2D problem along one axis. You iterate over rows and compute min, max, sum, or any aggregate. The same pattern applies when you need row sums for prefix sum problems or row maximums for monotonic stack problems on matrices.

2. Column-wise aggregation via transpose

The pattern of transposing a matrix to treat columns as rows:

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

Python does not have a built-in way to iterate over columns directly. The zip(*matrix) idiom fills that gap. Once you transpose, column operations become row operations, and you can reuse the same aggregation logic. This is useful in problems like Set Matrix Zeroes and any problem that needs both row and column properties.

3. Set intersection for cross-axis matching

The pattern of finding values that satisfy conditions along multiple axes:

result = row_set & col_set

When you have two independent conditions (one per axis), collecting candidates into sets and intersecting them is cleaner than nested loops. This O(1)-per-lookup approach avoids the O(m * n) cost of checking every cell against every column maximum.

Edge cases

Before submitting, think through these scenarios:

• 1x1 matrix: the single element is always both the row min and column max. It is always a lucky number.
• Single row: the minimum of the row is the only candidate. It is trivially the maximum of its column (the column has one element). Return it.
• Single column: the maximum of the column is the only candidate. It is trivially the minimum of its row. Return it.
• No lucky number: most matrices will not have a lucky number. The intersection of row mins and column maxes is empty, so you return an empty list.
• Lucky number in a corner: corners are the most common location for lucky numbers because they participate in both the smallest row and the largest column (or vice versa).

From understanding to recall

You have seen how the algorithm works: find row minimums, find column maximums, intersect. The logic is clean and the code fits in three lines. But producing those three lines from memory under pressure is a different skill.

The details that matter are small but important. Do you use min(row) or iterate manually? Do you remember that zip(*matrix) transposes? Do you use set intersection or loop through candidates? These are recall questions, not comprehension questions, and they are exactly what trips people up in interviews.

Spaced repetition is how you move from "I understand it" to "I can write it cold." You practice the row aggregation pattern, the transpose trick, and the set intersection from memory at increasing intervals. After a few rounds, you see "find elements satisfying row and column conditions" in a problem, and the template comes out automatically.

Related posts

• Set Matrix Zeroes - Another matrix problem where you track row and column properties independently, then apply changes based on both
• Spiral Matrix - Builds comfort with matrix traversal patterns and boundary tracking in 2D grids
• Search a 2D Matrix - Uses the sorted structure of rows and columns to perform efficient lookups in a matrix

CodeBricks breaks Lucky Numbers in a Matrix into its row aggregation, column transpose, and set intersection building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a matrix problem shows up in your interview, you do not think about it. You just write it.