Watch 10 video solutions for Lucky Numbers in a Matrix, a easy level problem involving Array, Matrix. This walkthrough by NeetCodeIO has 9,458 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.lengthn == mat[i].length1 <= n, m <= 501 <= matrix[i][j] <= 105.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 | Time | Space | When to Use |
|---|---|---|---|
| Iterative Row Minimum Check | O(m * (n + m)) | O(1) | Best when you want the simplest implementation with constant extra space |
| Mathematical Intersection | O(m * n) | O(m + n) | Preferred when reducing repeated column scans and keeping logic clean |