Lucky Numbers in a Matrix solution and explanation
Cisco
9 more videos on this problem
Lucky Numbers in a Matrix - Leetcode 1380 - PythonNeetCodeIO · 16:21 · 9K views
Lucky Numbers in a Matrix | 2 Approaches | Dry Run | Leetcode 1380 | codestorywithMIKcodestorywithMIK · 23:55 · 6K views
Leetcode Problem 1380 - Lucky Numbers in a MatrixRemy B99 · 12:07 · 1K views
Leetcode | 1380. Lucky Numbers in a Matrixapril mix · 5:08 · 558 views
Lucky Numbers in a Matrix - Leetcode 1380 - JavaCode With K5KC · 5:22 · 534 views
1380 Lucky Numbers in a Matrix Explained | Step-by-Step Solution | LeetCode |LeetQuestLeetQuest · 8:33 · 251 views
1380. Lucky Numbers in a Matrix - Javascript - Time: O(n) Space: O(n) - LeetcodeAaron Sadino Coding · 33:25 · 201 views
1380. Lucky Numbers in a Matrix | Leetcode | C++ - DSATechnosier · 11:22 · 181 views
1380. Lucky Numbers in a Matrix (LeetCode, Java)hakunamatasq · 7:05 · 130 views
Lucky Numbers in a Matrix | Leetcode 1380 | Java Code | Developer CoderDeveloper Coder · 14:27 · 128 views
The problem
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.- 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.
class Solution:
def luckyNumbers (self, matrix):
min_row = {min(row) for row in matrix}
max_col = {max(col) for col in zip(*matrix)}
return list(min_row & max_col)import java.util.ArrayList;
import java.util.List;
class Solution {
public List<Integer> luckyNumbers (int[][] matrix) {
List<Integer> result = new ArrayList<>();
int[] rowMin = new int[matrix.length];
for (int i = 0; i < matrix.length; i++) {
int minIndex = 0;
for (int j = 1; j < matrix[i].length; j++) {
if (matrix[i][j] < matrix[i][minIndex]) {
minIndex = j;
}
}
rowMin[i] = minIndex;
}
for (int j = 0; j < matrix[0].length; j++) {
int max = matrix[0][j];
for (int i = 0; i < matrix.length; i++) {
max = Math.max(max, matrix[i][j]);
}
for (int i = 0; i < matrix.length; i++) {
if (matrix[i][j] == max && j == rowMin[i]) {
result.add(matrix[i][j]);
}
}
}
return result;
}
}#include <vector>
#include <algorithm>
std::vector<int> luckyNumbers (std::vector<std::vector<int>>& matrix) {
std::vector<int> result;
std::vector<int> rowMin;
std::vector<bool> colMax(matrix[0].size(), true);
for (const auto& row : matrix) {
rowMin.push_back(*std::min_element(row.begin(), row.end()));
}
for (int j = 0; j < matrix[0].size(); ++j) {
int max_in_col = matrix[0][j];
for (int i = 0; i < matrix.size(); ++i) {
max_in_col = std::max(max_in_col, matrix[i][j]);
}
for (int i = 0; i < matrix.size(); ++i) {
if (matrix[i][j] == max_in_col && matrix[i][j] == rowMin[i]) {
result.push_back(matrix[i][j]);
}
}
}
return result;
}var luckyNumbers = function(matrix) {
let minRow = matrix.map(row => Math.min(...row));
let maxCol = Array(matrix[0].length).fill(Number.MIN_SAFE_INTEGER);
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[i].length; j++) {
maxCol[j] = Math.max(maxCol[j], matrix[i][j]);
}
}
return minRow.filter(val => maxCol.includes(val));
};#include <stdio.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
void luckyNumbers(int** mat, int matSize, int* matColSize, int* returnSize, int* returnArr){
int minRow[matSize];
for(int i = 0; i < matSize; i++){
minRow[i] = 0;
for(int j = 1; j < matColSize[i]; j++){
if(mat[i][j] < mat[i][minRow[i]]){
minRow[i] = j;
}
}
}
*returnSize = 0;
for(int j = 0; j < matColSize[0]; j++){
int isMax = 1;
int maxVal = mat[0][j];
for(int i = 0; i < matSize; i++){
if(mat[i][j] > maxVal){
maxVal = mat[i][j];
}
}
for(int i = 0; i < matSize; i++){
if(mat[i][j] == maxVal && j == minRow[i]){
returnArr[(*returnSize)++] = maxVal;
break;
}
}
}
}using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public IList<int> LuckyNumbers (int[][] matrix) {
List<int> result = new List<int>();
int m = matrix.Length;
int n = matrix[0].Length;
int[] minRow = new int[m];
for (int i = 0; i < m; i++) {
minRow[i] = int.MaxValue;
for (int j = 0; j < n; j++) {
minRow[i] = Math.Min(minRow[i], matrix[i][j]);
}
}
for (int j = 0; j < n; j++) {
int maxCol = int.MinValue;
for (int i = 0; i < m; i++) {
maxCol = Math.Max(maxCol, matrix[i][j]);
}
for (int i = 0; i < m; i++) {
if (matrix[i][j] == maxCol && matrix[i][j] == minRow[i]) {
result.Add(matrix[i][j]);
}
}
}
return result;
}
}Python's set operations allow an elegant solution. We find the minimum of each row and maximum of each column using set comprehension and then find the intersection.
Time Complexity: O(m * n) because we iterate through each element at most twice.
Space Complexity: O(m + n) for storing the row and column extrema.
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.
class Solution:
def luckyNumbersWithIntersections(self, matrix):
min_row = {min(row) for row in matrix}
max_col = [max(col) for col in zip(*matrix)]
return [num for num in min_row if num in max_col]import java.util.*;
class Solution {
public List<Integer> luckyNumbersWithSet (int[][] matrix) {
Set<Integer> rowMinSet = new HashSet<>();
for (int[] row : matrix) {
rowMinSet.add(Arrays.stream(row).min().getAsInt());
}
int[] colMax = new int[matrix[0].length];
Arrays.fill(colMax, Integer.MIN_VALUE);
for (int j = 0; j < matrix[0].length; j++) {
for (int i = 0; i < matrix.length; i++) {
colMax[j] = Math.max(colMax[j], matrix[i][j]);
}
}
List<Integer> luckyNumbers = new ArrayList<>();
for (int max : colMax) {
if (rowMinSet.contains(max)) {
luckyNumbers.add(max);
}
}
return luckyNumbers;
}
}#include <vector>
#include <unordered_set>
std::vector<int> luckyNumbersWithSet(std::vector<std::vector<int>>& matrix) {
std::unordered_set<int> minElements;
for (const auto& row : matrix) {
minElements.insert(*std::min_element(row.begin(), row.end()));
}
std::vector<int> maxCol(matrix[0].size(), 0);
for (int j = 0; j < matrix[0].size(); ++j) {
for (int i = 0; i < matrix.size(); ++i) {
maxCol[j] = std::max(maxCol[j], matrix[i][j]);
}
}
std::vector<int> luckyNumbers;
for (int j : maxCol) {
if (minElements.find(j) != minElements.end()) {
luckyNumbers.push_back(j);
}
}
return luckyNumbers;
}var luckyNumbers = function(matrix) {
let minRow = new Set(matrix.map(row => Math.min(...row)));
let maxCol = Array(matrix[0].length).fill(-Infinity);
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[i].length; j++) {
maxCol[j] = Math.max(maxCol[j], matrix[i][j]);
}
}
return [...minRow].filter(val => maxCol.includes(val));
};#include <stdbool.h>
#include <stdio.h>
void luckyNumbersMathematical(int** matrix, int matrixSize, int* matrixColSize, int* returnSize, int* returnArr){
bool isMaxInCol[*matrixColSize];
int minRow[matrixSize];
*returnSize = 0;
for (int i = 0; i < matrixSize; i++) {
minRow[i] = matrix[i][0];
for (int j = 1; j < matrixColSize[i]; j++) {
if (matrix[i][j] < minRow[i]) {
minRow[i] = matrix[i][j];
}
}
}
for (int j = 0; j < matrixColSize[0]; j++) {
int maxVal = matrix[0][j];
for (int i = 1; i < matrixSize; i++) {
if (matrix[i][j] > maxVal) maxVal = matrix[i][j];
}
for (int i = 0; i < matrixSize; i++) {
if (matrix[i][j] == maxVal && matrix[i][j] == minRow[i]) {
returnArr[(*returnSize)++] = matrix[i][j];
}
}
}
}using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public IList<int> LuckyNumbersWithSet(int[][] matrix) {
HashSet<int> rowMinSet = new HashSet<int>();
foreach (var row in matrix) {
rowMinSet.Add(row.Min());
}
int[] colMax = new int[matrix[0].Length];
Array.Fill(colMax, int.MinValue);
for (int j = 0; j < matrix[0].Length; j++) {
for (int i = 0; i < matrix.Length; i++) {
colMax[j] = Math.Max(colMax[j], matrix[i][j]);
}
}
List<int> luckyNumbers = new List<int>();
foreach (int max in colMax) {
if (rowMinSet.Contains(max)) {
luckyNumbers.Add(max);
}
}
return luckyNumbers;
}
}We utilize Python's powerful collection tools to directly find intersections between row minima and column maxima, yielding possible lucky numbers efficiently.
Time Complexity: O(m * n).
Space Complexity: O(m + n) due to our usage of lists and sets.
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.
function luckyNumbers(matrix: number[][]): number[] {
const m = matrix.length;
const n = matrix[0].length;
const rows: number[] = new Array(m).fill(1 << 30);
const cols: number[] = new Array(n).fill(0);
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; j++) {
rows[i] = Math.min(rows[i], matrix[i][j]);
cols[j] = Math.max(cols[j], matrix[i][j]);
}
}
const ans: number[] = [];
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; j++) {
if (rows[i] === cols[j]) {
ans.push(rows[i]);
}
}
}
return ans;
}func luckyNumbers(matrix [][]int) (ans []int) {
m, n := len(matrix), len(matrix[0])
rows, cols := make([]int, m), make([]int, n)
for i := range rows {
rows[i] = 1 << 30
}
for i, row := range matrix {
for j, x := range row {
rows[i] = min(rows[i], x)
cols[j] = max(cols[j], x)
}
}
for i, row := range matrix {
for j, x := range row {
if rows[i] == cols[j] {
ans = append(ans, x)
}
}
}
return
}impl Solution {
pub fn lucky_numbers(matrix: Vec<Vec<i32>>) -> Vec<i32> {
let m = matrix.len();
let n = matrix[0].len();
let mut res = vec![];
let mut col = vec![0; n];
for j in 0..n {
for i in 0..m {
col[j] = col[j].max(matrix[i][j]);
}
}
for x in 0..m {
let mut i = 0;
for y in 1..n {
if matrix[x][y] < matrix[x][i] {
i = y;
}
}
if matrix[x][i] == col[i] {
res.push(col[i]);
}
}
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(m * n) because we iterate through each element at most twice. |
| Mathematical Intersection | Time Complexity: O(m * n). |
| Maintain Row Minimum and Column Maximum | – |
Complexity analysis
| 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 |
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.