1380. Lucky Numbers in a Matrix

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.

Approach 01:

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    vector<int> luckyNumbers(vector<vector<int>>& matrix) {
        // Iterate through each row in the matrix
        for (const vector<int>& row : matrix) {
            // Find the index of the minimum element in the current row
            const int minElementIndex = distance(row.begin(), ranges::min_element(row));

            // Check if the minimum element in the row is the maximum element in
            // its column
            if (row[minElementIndex] == getMaxOfColumn(matrix, minElementIndex)){
                return {row[minElementIndex]};
            }
                
        }
        // Return an empty vector if no lucky number is found
        return {};
    }

private:
    // Helper function to find the maximum element in a specified column
    int getMaxOfColumn(const vector<vector<int>>& matrix, int colIndex) {
        int maxElement = 0;
        // Iterate through each row to find the maximum element in the column
        for (int rowIndex = 0; rowIndex < matrix.size(); ++rowIndex){
            maxElement = max(maxElement, matrix[rowIndex][colIndex]);
        }
        return maxElement;
    }
};

from typing import *

class Solution:
    def luckyNumbers(self, matrix: List[List[int]]) -> List[int]:
        # Iterate through each row in the matrix
        for row in matrix:
            # Find the index of the minimum element in the current row
            minElementIndex = row.index(min(row))

            # Check if the minimum element in the row is the maximum element in its column
            if row[minElementIndex] == self.getMaxOfColumn(matrix, minElementIndex):
                return [row[minElementIndex]]
        
        # Return an empty list if no lucky number is found
        return []

    # Helper function to find the maximum element in a specified column
    def getMaxOfColumn(self, matrix: List[List[int]], colIndex: int) -> int:
        maxElement = 0
        # Iterate through each row to find the maximum element in the column
        for row in matrix:
            maxElement = max(maxElement, row[colIndex])
        return maxElement

Time Complexity

• Finding Minimum Elements in Rows:

  Iterating through each row and finding the minimum element takes \( O(m \cdot n) \) time, where \( m \) is the number of rows and \( n \) is the number of columns. This is because for each of the \( m \) rows, finding the minimum element requires \( O(n) \) time.

• Finding Maximum Elements in Columns:

  For each row, checking if the minimum element is the maximum in its column requires iterating through all rows in that column, which takes \( O(m) \) time. This check is done at most \( m \) times, resulting in \( O(m \cdot m) = O(m^2) \) time.

• Overall Time Complexity:

  The overall time complexity is \( O(m \cdot n) \) for finding minimum elements plus \( O(m^2) \) for checking column maxima. Therefore, the total time complexity is \( O(m \cdot n) \).

Space Complexity

• Auxiliary Space:

  The algorithm uses a small amount of extra space for storing intermediate values like minElementIndex and maxElement, which are both \( O(1) \).

• Overall Space Complexity:

  The overall space complexity is \( O(1) \), as no additional data structures proportional to the input size are used.