Formatted question description: https://leetcode.ca/all/1380.html

1380. Lucky Numbers in a Matrix

Level

Easy

Description

Given a m * 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]

Constraints:

m == mat.length
n == mat[i].length
1 <= n, m <= 50
1 <= matrix[i][j] <= 10^5.
All elements in the matrix are distinct.

Algorithm

At the beginning, I thought of a brute force solution, searching whether each number meets such a limit, but found that this should be m^2 * n^2 time complexity, because it needs to traverse each element and traverse the current row and column at the same time.

But based on observations, we only need the minimum value of each row and the maximum value of each column, so that we can find one of them first and then look at the intersection. If it exists, it meets this requirement. This only needs to traverse each element of the matrix once.

Code

public class Lucky_Numbers_in_a_Matrix {

    // time:O(mn) space:O(m)
    // set intersection

    public List<Integer> luckyNumbers(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0)
            return new ArrayList<>();

        HashSet<Integer> minOfRows = new HashSet<>();
        for (int[] row : matrix) {
            int min = row[0];
            for (int n : row) {
                min = Math.min(min, n);
            }
            minOfRows.add(min);
        }

        int m = matrix.length;
        int n = matrix[0].length;
        List<Integer> res = new ArrayList<>();
        for (int j = 0; j < n; j++) {
            int max = matrix[0][j];
            for (int i = 0; i < m; i++) {
                max = Math.max(max, matrix[i][j]);
            }

            // intersection check
            if (minOfRows.contains(max)) res.add(max);
        }
        return res;
    }

}


############

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, Integer.MAX_VALUE);
        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(matrix[i][j]);
                }
            }
        }
        return ans;
    }
}

// OJ: https://leetcode.com/problems/lucky-numbers-in-a-matrix
// Time: O(MN)
// Space: O(M + N)
class Solution {
public:
    vector<int> luckyNumbers (vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size();
        vector<int> row(M, INT_MAX), col(N, INT_MIN);
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                row[i] = min(row[i], A[i][j]);
            }
        }
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                col[i] = max(col[i], A[j][i]);
            }
        }
        vector<int> ans;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] == row[i] && A[i][j] == col[j]) ans.push_back(A[i][j]);
            }
        }
        return ans;
    }
};

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)

func luckyNumbers (matrix [][]int) []int {
    m, n := len(matrix), len(matrix[0])
    rows, cols := make([]int, m), make([]int, n)
    for i := range rows {
        rows[i] = math.MaxInt32
    }
    for i, row := range matrix {
        for j, v := range row {
            rows[i] = min(rows[i], v)
            cols[j] = max(cols[j], v)
        }
    }
    var ans []int
    for i, row := range matrix {
        for j, v := range row {
            if rows[i] == cols[j] {
                ans = append(ans, v)
            }
        }
    }
    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

function luckyNumbers(matrix: number[][]): number[] {
    const m = matrix.length;
    const n = matrix[0].length;
    const col = new Array(n).fill(0);
    const res = [];
    for (let j = 0; j < n; j++) {
        for (let i = 0; i < m; i++) {
            col[j] = Math.max(col[j], matrix[i][j]);
        }
    }
    for (let x = 0; x < m; x++) {
        let i = 0;
        for (let y = 1; y < n; y++) {
            if (matrix[x][i] > matrix[x][y]) {
                i = y;
            }
        }
        if (matrix[x][i] === col[i]) {
            res.push(col[i]);
        }
    }
    return res;
}

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

Or, first, obtain the minimum value of each row and the column of the minimum values. Then, for each minimum value, check whether it is the maximum value in its column. If so, add it to the result list. Finally, return the result list.

class Solution {
    public List<Integer> luckyNumbers (int[][] matrix) {
        int rows = matrix.length, columns = matrix[0].length;
        int[] mins = new int[rows];
        for (int i = 0; i < rows; i++) {
            int min = matrix[i][0];
            int minColumn = 0;
            for (int j = 1; j < columns; j++) {
                if (matrix[i][j] < min) {
                    min = matrix[i][j];
                    minColumn = j;
                }
            }
            mins[i] = minColumn;
        }
        List<Integer> luckyNumbers = new ArrayList<Integer>();
        for (int i = 0; i < rows; i++) {
            int minColumn = mins[i];
            int min = matrix[i][minColumn];
            boolean flag = true;
            for (int j = 0; j < rows; j++) {
                if (j == i)
                    continue;
                else if (matrix[j][minColumn] > min) {
                    flag = false;
                    break;
                }
            }
            if (flag)
                luckyNumbers.add(min);
        }
        return luckyNumbers;
    }
}

############

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, Integer.MAX_VALUE);
        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(matrix[i][j]);
                }
            }
        }
        return ans;
    }
}

// OJ: https://leetcode.com/problems/lucky-numbers-in-a-matrix
// Time: O(MN)
// Space: O(M + N)
class Solution {
public:
    vector<int> luckyNumbers (vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size();
        vector<int> row(M, INT_MAX), col(N, INT_MIN);
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                row[i] = min(row[i], A[i][j]);
            }
        }
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < M; ++j) {
                col[i] = max(col[i], A[j][i]);
            }
        }
        vector<int> ans;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (A[i][j] == row[i] && A[i][j] == col[j]) ans.push_back(A[i][j]);
            }
        }
        return ans;
    }
};

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)

func luckyNumbers (matrix [][]int) []int {
    m, n := len(matrix), len(matrix[0])
    rows, cols := make([]int, m), make([]int, n)
    for i := range rows {
        rows[i] = math.MaxInt32
    }
    for i, row := range matrix {
        for j, v := range row {
            rows[i] = min(rows[i], v)
            cols[j] = max(cols[j], v)
        }
    }
    var ans []int
    for i, row := range matrix {
        for j, v := range row {
            if rows[i] == cols[j] {
                ans = append(ans, v)
            }
        }
    }
    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

function luckyNumbers(matrix: number[][]): number[] {
    const m = matrix.length;
    const n = matrix[0].length;
    const col = new Array(n).fill(0);
    const res = [];
    for (let j = 0; j < n; j++) {
        for (let i = 0; i < m; i++) {
            col[j] = Math.max(col[j], matrix[i][j]);
        }
    }
    for (let x = 0; x < m; x++) {
        let i = 0;
        for (let y = 1; y < n; y++) {
            if (matrix[x][i] > matrix[x][y]) {
                i = y;
            }
        }
        if (matrix[x][i] === col[i]) {
            res.push(col[i]);
        }
    }
    return res;
}

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

1380 - Lucky Numbers in a Matrix

1380. Lucky Numbers in a Matrix

Level

Description

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

1380. Lucky Numbers in a Matrix

Level

Description

Algorithm

Code

All Problems

All Solutions