LeetCode Problem 1380

Difficulty: 🟢 Easy
Topics: Array, Matrix

Solution

LeetCode 1380 - Lucky Numbers in a Matrix

Problem Understanding

This problem asks us to identify all lucky numbers in a given matrix.

A lucky number is defined as a value that satisfies two conditions simultaneously:

1. It must be the minimum value in its row
2. It must be the maximum value in its column

We are given an m x n matrix where every element is distinct, meaning no two numbers are the same. The goal is to return every element that qualifies as a lucky number. The result can be returned in any order.

Let us restate the problem in simpler terms.

For every element in the matrix, we want to determine whether it is the smallest number among all numbers in its row and also the largest number among all numbers in its column. If both conditions hold, we include it in the result.

For example, consider this matrix:

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

The minimum values of each row are:

3, 9, 15

The maximum values of each column are:

15, 16, 17

The only number that appears in both groups is 15, so it is the only lucky number.

The constraints tell us several useful things about the input size:

• 1 <= m, n <= 50, so the matrix is relatively small.
• Matrix values are distinct, which simplifies reasoning because we never need to handle ties.
• Values range up to 10^5, but their magnitude does not matter much because we only compare them.

Since the matrix size is at most 50 x 50, even moderately expensive approaches can work. However, we still want a clean and efficient solution.

Several edge cases are worth considering upfront.

A matrix may contain only one element. In that case, the single number is automatically both the row minimum and column maximum, so it must be returned.

A matrix may have only one row or one column. In a single row, the lucky number must be the row minimum and also the column maximum. In a single column, the lucky number must be the column maximum and row minimum.

The problem guarantees that all numbers are distinct, so we never need to worry about duplicate minimums or maximums causing ambiguity.

Approaches

Brute Force Approach

The most direct approach is to inspect every cell individually.

For each element matrix[i][j], we can:

1. Scan the entire row i to verify that the element is the minimum.
2. Scan the entire column j to verify that the element is the maximum.
3. If both conditions hold, add it to the answer.

This approach is straightforward and guaranteed to be correct because every candidate is explicitly validated against the problem definition.

However, it performs unnecessary repeated work. For every cell, we repeatedly scan rows and columns that overlap heavily with previous checks.

If there are m rows and n columns, each cell requires O(m + n) work, and there are m × n cells. This leads to a total complexity of:

O(m × n × (m + n))

Although the constraints are small enough for this to pass, we can do better.

Optimal Approach

The key observation is that a lucky number must belong to both of these sets:

• The set of row minimums
• The set of column maximums

Instead of repeatedly checking every candidate, we can precompute this information.

We first compute the minimum value of every row. Then we compute the maximum value of every column.

Once we have these two collections, any number that appears in both is a lucky number.

A set is useful here because it allows constant-time membership checks.

This avoids redundant scanning and makes the solution cleaner and more efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m × n × (m + n))	O(1)	Checks every element by rescanning row and column
Optimal	O(m × n)	O(m + n)	Precompute row minimums and column maximums

Algorithm Walkthrough

1. Compute the minimum value for each row.

Iterate through every row and find its minimum element. Store all row minimums in a set. We use a set because later we want fast membership checking. 2. Compute the maximum value for each column.

For each column index, scan all rows and determine the maximum element in that column. Store these values in another set. 3. Find common elements.

Iterate through the row minimum set and check whether each value also exists in the column maximum set. 4. Add matches to the result.

Any number appearing in both sets satisfies the lucky number definition, so add it to the result list. 5. Return the result.

Since the problem accepts any order, we can return the collected values directly.

Why it works

A lucky number must satisfy two independent properties simultaneously: being a row minimum and being a column maximum. By computing the complete set of row minimums and the complete set of column maximums, we guarantee that every valid lucky number appears in both sets. Likewise, any value appearing in both sets necessarily satisfies the exact definition of a lucky number. Therefore, the intersection of these two sets is precisely the correct answer.

Python Solution

from typing import List

class Solution:
    def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
        row_mins = {min(row) for row in matrix}

        rows = len(matrix)
        cols = len(matrix[0])

        col_maxes = set()

        for col in range(cols):
            max_value = matrix[0][col]

            for row in range(1, rows):
                max_value = max(max_value, matrix[row][col])

            col_maxes.add(max_value)

        return [num for num in row_mins if num in col_maxes]

The implementation closely follows the algorithm described above.

First, we compute the minimum element of every row using a set comprehension:

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

This gives us all candidates that satisfy the first requirement.

Next, we determine the maximum element of each column. Since Python matrices are represented as nested lists, we iterate column by column and scan through rows to compute the maximum value.

We store all column maximums in a set for efficient membership checks.

Finally, we compute the intersection implicitly using a list comprehension:

[num for num in row_mins if num in col_maxes]

Each number included satisfies both required conditions.

Go Solution

func luckyNumbers(matrix [][]int) []int {
	rows := len(matrix)
	cols := len(matrix[0])

	rowMins := make(map[int]bool)

	for _, row := range matrix {
		minValue := row[0]

		for _, value := range row {
			if value < minValue {
				minValue = value
			}
		}

		rowMins[minValue] = true
	}

	colMaxes := make(map[int]bool)

	for col := 0; col < cols; col++ {
		maxValue := matrix[0][col]

		for row := 1; row < rows; row++ {
			if matrix[row][col] > maxValue {
				maxValue = matrix[row][col]
			}
		}

		colMaxes[maxValue] = true
	}

	result := []int{}

	for num := range rowMins {
		if colMaxes[num] {
			result = append(result, num)
		}
	}

	return result
}

The Go implementation mirrors the Python solution closely. Since Go does not have a built-in set type, we simulate sets using map[int]bool.

Row minimums and column maximums are stored as map keys, allowing constant-time lookups.

Unlike Python, Go requires explicit loops to compute minimums and maximums. We also initialize slices explicitly before appending results.

Integer overflow is not a concern here because matrix values are bounded by 10^5, which fits comfortably within Go's integer range.

Worked Examples

Example 1

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

Step 1: Compute row minimums

Row	Values	Minimum
0	[3, 7, 8]	3
1	[9, 11, 13]	9
2	[15, 16, 17]	15

Result:

row_mins = {3, 9, 15}

Step 2: Compute column maximums

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

Result:

col_maxes = {15, 16, 17}

Step 3: Find intersection

{3, 9, 15} ∩ {15, 16, 17} = {15}

Answer:

[15]

Example 2

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

Step 1: Row minimums

Row	Minimum
[1,10,4,2]	1
[9,3,8,7]	3
[15,16,17,12]	12

row_mins = {1, 3, 12}

Step 2: Column maximums

Column	Values	Maximum
0	[1,9,15]	15
1	[10,3,16]	16
2	[4,8,17]	17
3	[2,7,12]	12

col_maxes = {15, 16, 17, 12}

Step 3: Intersection

{1, 3, 12} ∩ {15, 16, 17, 12} = {12}

Answer:

[12]

Example 3

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

Step 1: Row minimums

row_mins = {7, 1}

Step 2: Column maximums

col_maxes = {7, 8}

Step 3: Intersection

{7, 1} ∩ {7, 8} = {7}

Answer:

[7]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n)	Each matrix cell is processed a constant number of times
Space	O(m + n)	Stores row minimums and column maximums

The algorithm scans the matrix twice, once for row minimums and once for column maximums. Since each cell contributes only constant work during these scans, the total running time is O(m × n).

The extra space comes from storing up to m row minimums and n column maximums.

Test Cases

class Solution:
    def luckyNumbers(self, matrix):
        row_mins = {min(row) for row in matrix}

        rows = len(matrix)
        cols = len(matrix[0])

        col_maxes = set()

        for col in range(cols):
            max_value = matrix[0][col]

            for row in range(1, rows):
                max_value = max(max_value, matrix[row][col])

            col_maxes.add(max_value)

        return [num for num in row_mins if num in col_maxes]

solution = Solution()

assert sorted(solution.luckyNumbers([[3,7,8],[9,11,13],[15,16,17]])) == [15]  # Example 1
assert sorted(solution.luckyNumbers([[1,10,4,2],[9,3,8,7],[15,16,17,12]])) == [12]  # Example 2
assert sorted(solution.luckyNumbers([[7,8],[1,2]])) == [7]  # Example 3

assert sorted(solution.luckyNumbers([[42]])) == [42]  # Single element matrix
assert sorted(solution.luckyNumbers([[1,2,3,4]])) == [1]  # Single row
assert sorted(solution.luckyNumbers([[1],[2],[3]])) == [3]  # Single column

assert sorted(solution.luckyNumbers([[5,1],[4,2]])) == [4]  # Lucky number in first column
assert sorted(solution.luckyNumbers([[8,6],[7,5]])) == [7]  # Small matrix variation
assert sorted(solution.luckyNumbers([[20,10,30],[5,15,25],[35,40,45]])) == []  # No lucky number

Test	Why
[[3,7,8],[9,11,13],[15,16,17]]	Verifies Example 1
[[1,10,4,2],[9,3,8,7],[15,16,17,12]]	Verifies Example 2
[[7,8],[1,2]]	Verifies Example 3
[[42]]	Tests smallest possible matrix
[[1,2,3,4]]	Tests single-row behavior
[[1],[2],[3]]	Tests single-column behavior
[[5,1],[4,2]]	Verifies lucky number in first column
[[8,6],[7,5]]	Tests a small non-trivial matrix
[[20,10,30],[5,15,25],[35,40,45]]	Tests case with no lucky number

Edge Cases

Single Element Matrix

A 1 x 1 matrix is the simplest possible input. The lone value is automatically the minimum in its row and the maximum in its column because no other elements exist. A naive implementation might accidentally mishandle indexing assumptions, but this implementation works naturally because both the row minimum and column maximum sets contain the same value.

Single Row or Single Column

When the matrix has only one row, the lucky number must be the row minimum because every element is automatically a column maximum of its own column only if no larger values exist below. Similarly, in a single-column matrix, the lucky number becomes the maximum element in the column while also being the minimum of its row. The algorithm handles both cases without special logic.

No Lucky Number Exists

Although many examples contain one lucky number, some matrices may contain none. An incorrect implementation might assume there is always a result. Here, if the intersection between row minimums and column maximums is empty, the algorithm simply returns an empty list.

Distinct Values Guarantee

The problem guarantees that all numbers are distinct. This avoids ambiguity when identifying minimums and maximums. Our implementation does not rely heavily on this guarantee, but it ensures there are no ties that could complicate reasoning about lucky numbers.