Question

1380. Lucky Numbers in a Matrix

中文文档

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

Solutions

Solution 1: Maintain Row Minimum and Column Maximum

We can use two arrays $rows$ and $cols$ to record the minimum value of each row and the maximum value of each column in the matrix. Then, we traverse each element in the matrix, checking whether this element is the minimum value of its row and the maximum value of its column. If it is, then this element is a lucky number, and we add it to the answer array.

After the traversal is finished, we return the answer array.

The time complexity is $O(m \times n)$, and the space complexity is $O(m + n)$. Where $m$ and $n$ are the number of rows and columns in the matrix, respectively.

class Solution:
  def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
    rows = {min(row) for row in matrix}
    cols = {max(col) for col in zip(*matrix)}
    return list(rows & cols)

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;
  }
}

class Solution {
public:
  vector<int> luckyNumbers(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    int rows[m];
    int cols[n];
    memset(rows, 0x3f, sizeof(rows));
    memset(cols, 0, sizeof(cols));
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        rows[i] = min(rows[i], matrix[i][j]);
        cols[j] = max(cols[j], matrix[i][j]);
      }
    }
    vector<int> ans;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (rows[i] == cols[j]) {
          ans.push_back(rows[i]);
        }
      }
    }
    return ans;
  }
};

func luckyNumbers(matrix [][]int) (ans []int) {
  m, n := len(matrix), len(matrix[0])
  rows, cols := make([]int, m), make([]int, n)
  for i := range rows {
    rows[i] = 1 << 30
  }
  for i, row := range matrix {
    for j, x := range row {
      rows[i] = min(rows[i], x)
      cols[j] = max(cols[j], x)
    }
  }
  for i, row := range matrix {
    for j, x := range row {
      if rows[i] == cols[j] {
        ans = append(ans, x)
      }
    }
  }
  return
}

function luckyNumbers(matrix: number[][]): number[] {
  const m = matrix.length;
  const n = matrix[0].length;
  const rows: number[] = new Array(m).fill(1 << 30);
  const cols: number[] = new Array(n).fill(0);
  for (let i = 0; i < m; ++i) {
    for (let j = 0; j < n; j++) {
      rows[i] = Math.min(rows[i], matrix[i][j]);
      cols[j] = Math.max(cols[j], matrix[i][j]);
    }
  }
  const ans: number[] = [];
  for (let i = 0; i < m; ++i) {
    for (let j = 0; j < n; j++) {
      if (rows[i] === cols[j]) {
        ans.push(rows[i]);
      }
    }
  }
  return ans;
}

impl Solution {
  pub fn lucky_numbers(matrix: Vec<Vec<i32>>) -> Vec<i32> {
    let m = matrix.len();
    let n = matrix[0].len();
    let mut res = vec![];
    let mut col = vec![0; n];
    for j in 0..n {
      for i in 0..m {
        col[j] = col[j].max(matrix[i][j]);
      }
    }
    for x in 0..m {
      let mut i = 0;
      for y in 1..n {
        if matrix[x][y] < matrix[x][i] {
          i = y;
        }
      }
      if matrix[x][i] == col[i] {
        res.push(col[i]);
      }
    }
    res
  }
}