Lucky Numbers in a Matrix

Easy
282.

Lucky Numbers in a Matrix

Lucky Numbers in a Matrix is an easy coding problem on arrays and matrix, asked in Amazon and Adobe interviews.

Given an m × n matrix of distinct numbers, return all the lucky numbers, in row order.

A lucky number is an element that is the minimum of its row and the maximum of its column.

Example 1

Input
matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output
[15]
Explanation
15 is the smallest in its row and the largest in its column.

Example 2

Input
matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output
[12]

Example 3

Input
matrix = [[7,8],[1,2]]
Output
[7]

Constraints

  • 1 <= matrix.length, matrix[i].length <= 8
  • 1 <= matrix[i][j] <= 100000
  • All elements are distinct.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var luckyNumbers = function(matrix) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Lucky Numbers in a Matrix — Solution in Python, Java & C++

Lucky Numbers in a Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Lucky Numbers in a Matrix is an easy coding problem on arrays and matrix, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Arrays, Matrix
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an m × n matrix of distinct numbers, return all the lucky numbers, in row order.

A lucky number is an element that is the minimum of its row and the maximum of its column.

Example 1

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the smallest in its row and the largest in its column.

Example 2

Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output: [12]

Example 3

Input: matrix = [[7,8],[1,2]]
Output: [7]

Constraints

  • 1 <= matrix.length, matrix[i].length <= 8
  • 1 <= matrix[i][j] <= 100000
  • All elements are distinct.

Hints for Lucky Numbers in a Matrix

  1. Hint 1

    Find the minimum of each row, then check whether it also dominates its column.

  2. Hint 2

    Because the values are distinct, at most one lucky number can exist — but scanning every row is still the clearest way to find it.

  3. Hint 3

    Alternatively, intersect the set of row minima with the set of column maxima.

How to solve Lucky Numbers in a Matrix

Collect the minimum of every row and the maximum of every column; a lucky number is in both sets.

Approach

  1. Build the set of row minima.
  2. Build the set of column maxima.
  3. Walk the matrix in row order and emit values in both sets.

Why it works

The definition is exactly the intersection of those two properties, and distinct values mean a set lookup identifies the cell unambiguously.

Complexity

  • Time — O(m · n)
  • Space — O(m + n)

Pitfalls

  • At most one lucky number can exist when values are distinct, but the scan is still the clearest formulation.

Reference solution

Python

def luckyNumbers(matrix):
    row_min = {min(row) for row in matrix}
    col_max = {max(col) for col in zip(*matrix)}
    return [v for row in matrix for v in row if v in row_min and v in col_max]

Java

public static int[] luckyNumbers(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    List<Integer> out = new ArrayList<>();
    for (int r = 0; r < m; r++) {
        int minC = 0;
        for (int c = 1; c < n; c++) {
            if (matrix[r][c] < matrix[r][minC]) minC = c;
        }
        boolean isMax = true;
        for (int rr = 0; rr < m; rr++) {
            if (matrix[rr][minC] > matrix[r][minC]) { isMax = false; break; }
        }
        if (isMax) out.add(matrix[r][minC]);
    }
    int[] res = new int[out.size()];
    for (int i = 0; i < res.length; i++) res[i] = out.get(i);
    return res;
}

C++

vector<int> luckyNumbers(vector<vector<int>>& matrix) {
    int m = (int) matrix.size(), n = (int) matrix[0].size();
    vector<int> out;
    for (int r = 0; r < m; r++) {
        int minC = 0;
        for (int c = 1; c < n; c++) {
            if (matrix[r][c] < matrix[r][minC]) minC = c;
        }
        bool isMax = true;
        for (int rr = 0; rr < m; rr++) {
            if (matrix[rr][minC] > matrix[r][minC]) { isMax = false; break; }
        }
        if (isMax) out.push_back(matrix[r][minC]);
    }
    return out;
}

JavaScript

var luckyNumbers = function(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const out = [];
    for (let r = 0; r < m; r++) {
        let minC = 0;
        for (let c = 1; c < n; c++) {
            if (matrix[r][c] < matrix[r][minC]) minC = c;
        }
        let isMax = true;
        for (let rr = 0; rr < m; rr++) {
            if (matrix[rr][minC] > matrix[r][minC]) { isMax = false; break; }
        }
        if (isMax) out.push(matrix[r][minC]);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal