Scale Engineer

Lucky Numbers in a Matrix

Easy
#1279Time: 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: O(1) auxiliary space, not counting the space for the output list.1 company
Data structures
ArrayMatrix
Companies
Cisco

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

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

O(1) auxiliary space, not counting the space for the output list.

Trade-offs

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).

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem