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.

Examples

Example 1:

$$ matrix = \begin{bmatrix} 3 & 7 & 8 \\ 9 & 11 & 13 \\ \colorbox{green} {15} & 16 & 17 \end{bmatrix} $$

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:

$$ matrix = \begin{bmatrix} 1 & 10 & 4 & 2 \\ 9 & 3 & 8 & 7 \\ 15 & 16 & 17 & \colorbox{green} {12} \end{bmatrix} $$

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:

$$ matrix = \begin{bmatrix} \colorbox{green} {7} & 8 \\ 1 & 2 \end{bmatrix} $$

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.

Solution

Method 1 - Two Pass

Here is the step by step approach:

  1. Find Minimum Elements in Each Row: Traverse each row and keep track of the minimum element in that row.
  2. Find Maximum Elements in Each Column: Traverse each column and keep track of the maximum element in that column.
  3. Identify Lucky Numbers: For each row, check if the minimum element in that row is also the maximum element in its column. If it is, it’s a lucky number.

Pseudocode

function findLuckyNumbers(matrix):
    initialize rowMins as empty list
    initialize colMaxs as empty list with length of n and initialized to very small values
 
    for each row in matrix:
        find the minimum element in the row and append to rowMins
 
    for each column in matrix:
        find the maximum element in the column and store in colMaxs
 
    initialize luckyNumbers as empty list
    for each element in rowMins:
        if element is in colMaxs:
            append element to luckyNumbers
 
    return luckyNumbers

Video

Here is the video explanation:

Code

Java
public class Solution {

	public List<Integer> luckyNumbers(int[][] matrix) {
		int m = matrix.length;
		int n = matrix[0].length;

		int[] rowMins = new int[m];
		int[] colMaxs = new int[n];

		// Initialize rowMins with maximum values and colMaxs with minimum values
		Arrays.fill(rowMins, Integer.MAX_VALUE);
		Arrays.fill(colMaxs, Integer.MIN_VALUE);

		// Step 1 and Step 2 combined: Find the minimum element in each row and
		// the maximum element in each column in a single pass
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				rowMins[i] = Math.min(rowMins[i], matrix[i][j]);
				colMaxs[j] = Math.max(colMaxs[j], matrix[i][j]);
			}
		}

		// Step 3: Find all lucky numbers
		List<Integer> luckyNumbers = new ArrayList<>();

		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (matrix[i][j] == rowMins[i] && matrix[i][j] == colMaxs[j]) {
					luckyNumbers.add(matrix[i][j]);
				}
			}
		}

		return luckyNumbers;
	}
}
Python
def findLuckyNumbers(matrix):
    if not matrix or not matrix[0]:
        return []

    m, n = len(matrix), len(matrix[0])

    # Step 1: Find the minimum element in each row
    rowMins = [min(row) for row in matrix]

    # Step 2: Find the maximum element in each column
    colMaxs = [max(column) for column in zip(*matrix)]

    # Step 3: Find all lucky numbers
    luckyNumbers = []
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == rowMins[i] and matrix[i][j] == colMaxs[j]:
                luckyNumbers.append(matrix[i][j])

    return luckyNumbers

Complexity

  • ⏰ Time complexity: O(m*n) where m is number of rows, and n is number of columns.
  • 🧺 Space complexity: O(m + n)

Dry Run

Lets take eg. 1, with matrix: $$ matrix = \begin{bmatrix} 3 & 7 & 8 \\ 9 & 11 & 13 \\ 15 & 16 & 17 \end{bmatrix} $$ In first pass, we get, rowMins = [3, 9, 15] and colMaxs = 15, 16, 17. In second pass, we get, only 15 as lucky number, as rowMins[2] == 15 and colMaxs[0] == 15.