{x}
blog image

Lucky Numbers in a Matrix

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.

Solution Explanation and Code for Finding Lucky Numbers in a Matrix

This problem asks to find all "lucky numbers" within a given matrix. A lucky number is defined as an element that's both the minimum value in its row and the maximum value in its column.

The most efficient approach is a two-pass algorithm:

1. Finding Row Minimums and Column Maximums:

  • We iterate through the matrix once.
  • For each row, we track its minimum value.
  • For each column, we track its maximum value. This can be done efficiently using zip(*matrix) in Python (transposing the matrix) or similar techniques in other languages.

2. Identifying Lucky Numbers:

  • We iterate through the matrix again.
  • For each element, we check if it matches both the minimum of its row and the maximum of its column.
  • If it does, it's a lucky number, and we add it to the result list.

Time Complexity: O(m*n), where 'm' is the number of rows and 'n' is the number of columns. We iterate through the matrix twice.

Space Complexity: O(m+n). We use arrays (or sets in Python's case) of size 'm' and 'n' to store row minimums and column maximums respectively.

Code Implementations:

Python3:

class Solution:
    def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
        rows = {min(row) for row in matrix}  #Set for efficient lookup
        cols = {max(col) for col in zip(*matrix)} #Zip transposes the matrix
        return list(rows & cols) #Intersection of sets finds lucky numbers

Java:

import java.util.*;
class Solution {
    public List<Integer> luckyNumbers (int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[] rowMin = new int[m];
        int[] colMax = new int[n];
        Arrays.fill(rowMin, Integer.MAX_VALUE); //Initialize with maximum possible int value
 
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                rowMin[i] = Math.min(rowMin[i], matrix[i][j]);
                colMax[j] = Math.max(colMax[j], matrix[i][j]);
            }
        }
 
        List<Integer> result = new ArrayList<>();
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(matrix[i][j] == rowMin[i] && matrix[i][j] == colMax[j]){
                    result.add(matrix[i][j]);
                }
            }
        }
        return result;
    }
}

C++:

#include <vector>
#include <algorithm>
 
using namespace std;
 
class Solution {
public:
    vector<int> luckyNumbers(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<int> rowMin(m, INT_MAX); //Initialize with maximum possible int value
        vector<int> colMax(n, INT_MIN); //Initialize with minimum possible int value
 
 
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                rowMin[i] = min(rowMin[i], matrix[i][j]);
                colMax[j] = max(colMax[j], matrix[i][j]);
            }
        }
 
        vector<int> result;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == rowMin[i] && matrix[i][j] == colMax[j]) {
                    result.push_back(matrix[i][j]);
                }
            }
        }
        return result;
    }
};

Go:

func luckyNumbers(matrix [][]int) []int {
	m, n := len(matrix), len(matrix[0])
	rowMin := make([]int, m)
	colMax := make([]int, n)
	for i := 0; i < m; i++ {
		rowMin[i] = math.MaxInt32
	}
 
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			rowMin[i] = min(rowMin[i], matrix[i][j])
			colMax[j] = max(colMax[j], matrix[i][j])
		}
	}
 
	var result []int
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if matrix[i][j] == rowMin[i] && matrix[i][j] == colMax[j] {
				result = append(result, matrix[i][j])
			}
		}
	}
	return result
}

The other languages (TypeScript, JavaScript, Rust) would follow a similar structure, adapting the array/list handling and min/max functions to their respective syntax. The core algorithm remains consistent.