Skip to main content
Talentd

Lucky Numbers in a Matrix - Solution & Explanation

EasyArrayMatrix17 min readAsked at: Amazon, Oracle, Cisco
Practice this problem

Problem Statement

Given an m x n matrix of distinct numbers, return all lucky numbers in the matrix in any order.

A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.

 

Example 1:

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 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]
Explanation: 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]
Explanation: 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.

Approach Overview

Problem Overview: You receive an m x n matrix and must return all lucky numbers. A lucky number is an element that is the minimum in its row and the maximum in its column. The task is to scan the matrix efficiently and identify elements that satisfy both conditions.

Approach 1: Iterative Row Minimum Check (O(m * (n + m)) time, O(1) space)

Iterate through each row and find the minimum value along with its column index. Once you have the row minimum, scan that column to verify whether the same value is also the maximum element in that column. The logic is straightforward: a lucky number must survive both checks. This approach uses simple iteration over the array representation of the matrix and avoids extra memory. Time complexity becomes O(m * (n + m)) because each row scan costs O(n) and the column validation costs O(m). Space complexity remains O(1).

Approach 2: Mathematical Intersection (O(m * n) time, O(m + n) space)

A lucky number must belong to two sets: the set of all row minimums and the set of all column maximums. First compute an array of row minimum values and another array of column maximum values by scanning the matrix. Then iterate through the matrix again and check if matrix[i][j] == rowMin[i] and matrix[i][j] == colMax[j]. If both conditions hold, the value is a lucky number. The key insight is treating the problem as an intersection between two computed properties of the grid. The total runtime is O(m * n) because each element is processed a constant number of times, and the additional storage for row and column arrays is O(m + n).

Recommended for interviews: The iterative row-minimum check is usually the first solution interviewers expect because it demonstrates clear reasoning about matrix traversal. The intersection method is cleaner for larger matrices and shows you understand how to precompute properties to reduce repeated work. Both rely on basic array and matrix traversal patterns commonly tested in interviews.

Approach 1: Iterative Approach

This approach involves two main steps. First, find the minimum element in each row and keep track of the potential lucky numbers. Then, verify these potential numbers to check if they are the maximum in their respective columns.

This C program identifies lucky numbers by first finding the index of the minimum in each row. Then it checks those values across columns to ascertain if they're maximums within their respective columns.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the matrix.
Space Complexity: O(m) for storing the minimum indices for each row.

Try this approach in the editor →

Approach 2: Mathematical Intersection

This approach leverages set operations from mathematics to identify potential lucky numbers. We extract the row minimums and column maximums into separate sets and find the intersection of these sets for possible lucky numbers.

This C implementation performs a mathematical check for intersection by keeping potential lucky values in a temporary array, then validating if they appear within the maximums of their columns.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns.
Space Complexity: O(n) for storing column maximums.

Try this approach in the editor →

Approach 3: 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.

After the traversal is finished, we return the answer array.

The time complexity is O(m times n), and the space complexity is O(m + n). Where m and n are the number of rows and columns in the matrix, respectively.

Code

PythonJavaC++GoTypeScriptJavaScriptRust

Python

Java

C++

Go

TypeScript

JavaScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Approach

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the matrix.
Space Complexity: O(m) for storing the minimum indices for each row.

Mathematical Intersection

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns.
Space Complexity: O(n) for storing column maximums.

Maintain Row Minimum and Column Maximum—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Row Minimum CheckO(m * (n + m))O(1)Best when you want the simplest implementation with constant extra space
Mathematical IntersectionO(m * n)O(m + n)Preferred when reducing repeated column scans and keeping logic clean

Video Solution

Lucky Numbers in a Matrix - Leetcode 1380 - Python • NeetCodeIO • 9,627 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Lucky Numbers in a Matrix easy or hard?
Lucky Numbers in a Matrix is categorized as an Easy problem on LeetCode with a high acceptance rate around 79%. The challenge focuses on correctly identifying row minimum and column maximum relationships rather than complex algorithms.
Lucky Numbers in a Matrix Python/Java solution
Python and Java implementations typically iterate through rows to find the minimum element and then validate whether it is the maximum in its column. The logic translates directly across languages using simple loops and constant extra space.
How to solve Lucky Numbers in a Matrix in O(m*n)?
Compute two arrays: one storing the minimum element of each row and another storing the maximum element of each column. Then iterate through the matrix and check if matrix[i][j] equals both rowMin[i] and colMax[j]. Each element is processed a constant number of times, resulting in O(m * n) time complexity.
What is the best approach for Lucky Numbers in a Matrix?
The most common solution scans each row to find its minimum and then verifies whether that value is the maximum in its column. This approach runs in O(m * (n + m)) time with O(1) extra space. Another clean solution precomputes row minimums and column maximums and checks their intersection in O(m * n) time.
Is Lucky Numbers in a Matrix asked at Google/Amazon/Meta?
Matrix traversal and row/column property problems appear frequently in technical interviews at companies like Amazon and Google. While this exact problem may vary, the underlying pattern of computing row minimums and column maximums is a common interview concept.
What data structure is used in Lucky Numbers in a Matrix?
The problem primarily uses a 2D array (matrix). Some optimized solutions also use auxiliary arrays to store row minimums and column maximums, which help reduce repeated scans and keep the algorithm linear.
What is the time complexity of Lucky Numbers in a Matrix?
The typical iterative solution runs in O(m * (n + m)) time because each row scan takes O(n) and each column validation takes O(m). With a precomputation approach using row minimum and column maximum arrays, the runtime becomes O(m * n) with O(m + n) extra space.

Ready to solve this problem?

Practice Lucky Numbers in a Matrix with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays