Lucky Numbers in a Matrix

EASY

Description

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] <= 10⁵.
All elements in the matrix are distinct.

Approaches

Checkout 3 different approaches to solve Lucky Numbers in a Matrix. Click on different approaches to view the approach and algorithm in detail.

Optimized Row-wise Check

This approach improves upon the brute-force method by reducing redundant checks. Instead of checking every element, we first identify the minimum element in each row. Only these row-minimums are candidates for being lucky numbers. Then, for each of these candidates, we check if it is the maximum in its respective column.

Algorithm

Initialize an empty list luckyNumbers.
Iterate through each row i from 0 to m-1.
Find the minimum value minVal and its column index minIndex in the current row i.
Assume minVal is a lucky number (i.e., it's the maximum in its column). Let isMaxInCol = true.
Iterate through each row k from 0 to m-1 to check column minIndex.

If `matrix[k][minIndex] > minVal`, then `minVal` is not the maximum in its column. Set `isMaxInCol = false` and break the inner loop.

If isMaxInCol remains true after checking the entire column, add minVal to the luckyNumbers list.
Return luckyNumbers.

The algorithm iterates through each row of the matrix one by one. For each row i, it finds the minimum value minVal and its column index minIndex. This is done with a single scan of the row. Once the row minimum minVal is found, it is a potential lucky number. The first condition (minimum in its row) is already satisfied. The next step is to verify the second condition: whether minVal is the maximum element in its column minIndex. To do this, we iterate through all elements in column minIndex and compare them with minVal. If no element in the column is greater than minVal, it satisfies the second condition and is added to the result list. This process is repeated for all rows.

import java.util.ArrayList;
import java.util.List;

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

        for (int i = 0; i < m; i++) {
            // Find the minimum element in the current row
            int minVal = matrix[i][0];
            int minIndex = 0;
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] < minVal) {
                    minVal = matrix[i][j];
                    minIndex = j;
                }
            }

            // Check if this element is the maximum in its column
            boolean isMaxInCol = true;
            for (int k = 0; k < m; k++) {
                if (matrix[k][minIndex] > minVal) {
                    isMaxInCol = false;
                    break;
                }
            }

            if (isMaxInCol) {
                luckyNumbers.add(minVal);
            }
        }
        return luckyNumbers;
    }
}

Complexity Analysis

Time Complexity: O(m * (n + m)). For each of the `m` rows, we spend `O(n)` to find the minimum and `O(m)` to check the column.Space Complexity: O(1) auxiliary space, not counting the space for the output list.

Pros and Cons

Pros:

More efficient than the pure brute-force approach.
Still maintains low space complexity.

Cons:

Can still be slow if the number of rows (m) is large, as the complexity is O(m*n + m^2).

Code Solutions

Checking out 4 solutions in different languages for Lucky Numbers in a Matrix. Click on different languages to view the code.

class Solution {
public
  List<Integer> luckyNumbers(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int[] rows = new int[m];
    int[] cols = new int[n];
    Arrays.fill(rows, 1 << 30);
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        rows[i] = Math.min(rows[i], matrix[i][j]);
        cols[j] = Math.max(cols[j], matrix[i][j]);
      }
    }
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (rows[i] == cols[j]) {
          ans.add(rows[i]);
        }
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Lucky Numbers in a Matrix

Data Structures:

ArrayMatrix

Companies:

Cisco |