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

Java

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

}

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.

Java

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

All Problems

All Solutions