LeetCode – 1380. Lucky number in matrix

I give you an m by n matrix with different numbers in it. Return all lucky numbers in the matrix in any order.

A lucky number is an element in a matrix that satisfies both the following conditions:

  • Smallest of all elements in the same row
  • The largest of all elements in the same column

Example 1:

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]] output: [15] explanation: 15 is the only lucky number because it is the minimum value in its row and the maximum value in its column.Copy the code

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 because it is the smallest value in its row and the largest value in its column.Copy the code

Example 3:

Matrix = [[7,8],[1,2]]Copy the code

Tip:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= n, m <= 50
  • 1 <= matrix[i][j] <= 10^5
  • All the elements of a matrix are different

Their thinking

Solution one: according to the lucky number definition search

  1. Loop through the matrix matrix to get the smallest element in each row
  2. Determine whether the element obtained in the first step is the largest element in the column
/ * * *@param {number[][]} matrix
 * @return {number[]}* /
var luckyNumbers  = function(matrix) {
    // Find by lucky number definition
    let m = matrix.length, n = matrix[0].length, lucky = []
    // loop matrix matrix
    for (let i = 0; i < m; i++) {
        // Find the smallest element in the row and record its value and column index
        let min = matrix[i][0], ind = 0
        for (let j = 1; j < n; j++) {
            if (matrix[i][j] < min) {
                min = matrix[i][j]
                ind = j
            }
        }
        // Determine if it is the largest element in the column
        for (let j = 0; j < m; j++) {
            // There is a greater value, terminate
            if (matrix[j][ind] > min) break
            // Join lucky
            if (j == m - 1) lucky.push(min)
        }
    }
    return lucky
};
Copy the code

Solution two: get the minimum and maximum set

  1. Gets the minimum value in each row element
  2. Gets the maximum value in each column element
  3. Find the intersection of minimum and maximum sets
/ * * *@param {number[][]} matrix
 * @return {number[]}* /
var luckyNumbers  = function(matrix) {
    // Get the minimum set of values for each row
    let mins = matrix.map(row= > Math.min(... row))// Get the set of maximum values for each column
    let maxs = matrix[0].map((item, col_index) = > Math.max(... matrix.map(row= > row[col_index])))
    // The intersection of the minimum and maximum sets is a lucky number
    return maxs.filter(item= > mins.includes(item))
};
Copy the code