1380. Lucky Numbers in a Matrix

[mah-shamim]

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.

Hint:

1. Find out and save the minimum of each row and maximum of each column in two lists.
2. Then scan through the whole matrix to identify the elements that satisfy the criteria.

[mah-shamim]

To solve this problem, we can follow these steps:

1. Identify Row Minimums: For each row, find the minimum element.
2. Identify Column Maximums: For each column, find the maximum element.
3. Check for Lucky Numbers: Traverse the matrix and check if an element is both the minimum in its row and the maximum in its column.

Let's implement this solution in PHP: 1380. Lucky Numbers in a Matrix

<?PHP

/**
     * @param Integer[][] $matrix
     * @return Integer[]
     */
    function luckyNumbers ($matrix) {
        $m = count($matrix);
        $n = count($matrix[0]);

        $rowMins = [];
        $colMaxs = array_fill(0, $n, PHP_INT_MIN);

        // Find the minimum in each row
        for ($i = 0; $i < $m; $i++) {
            $rowMins[$i] = PHP_INT_MAX;
            for ($j = 0; $j < $n; $j++) {
                if ($matrix[$i][$j] < $rowMins[$i]) {
                    $rowMins[$i] = $matrix[$i][$j];
                }
            }
        }

        // Find the maximum in each column
        for ($j = 0; $j < $n; $j++) {
            for ($i = 0; $i < $m; $i++) {
                if ($matrix[$i][$j] > $colMaxs[$j]) {
                    $colMaxs[$j] = $matrix[$i][$j];
                }
            }
        }

        $luckyNumbers = [];

        // Check for lucky numbers
        for ($i = 0; $i < $m; $i++) {
            for ($j = 0; $j < $n; $j++) {
                if ($matrix[$i][$j] == $rowMins[$i] && $matrix[$i][$j] == $colMaxs[$j]) {
                    $luckyNumbers[] = $matrix[$i][$j];
                }
            }
        }

        return $luckyNumbers;
    }

// Example usage:
$matrix1 = [[3,7,8],[9,11,13],[15,16,17]];
$matrix2 = [[1,10,4,2],[9,3,8,7],[15,16,17,12]];
$matrix3 = [[7,8],[1,2]];

print_r(luckyNumbers($matrix1)); // Output: [15]
print_r(luckyNumbers($matrix2)); // Output: [12]
print_r(luckyNumbers($matrix3)); // Output: [7]

?>

Explanation:

1. Initialization:

   • $rowMins stores the minimum element for each row.
   • $colMaxs stores the maximum element for each column, initialized to the smallest possible value.

2. Finding Row Minimums:

   • Iterate over each row, find the minimum element and store it in $rowMins.

3. Finding Column Maximums:

   • Iterate over each column, find the maximum element and store it in $colMaxs.

4. Checking for Lucky Numbers:

   • Iterate over the entire matrix.
   • If an element is equal to the minimum in its row ($rowMins[$i]) and the maximum in its column ($colMaxs[$j]), add it to the list of lucky numbers.

This approach ensures that we correctly identify all lucky numbers in the matrix with a time complexity of (O(m \times n)), which is efficient for the given constraints.