Lucky Numbers in a Matrix

Problem Statement

In the given problem, we need to find and return all "lucky numbers" from an m x n matrix of distinct integers. A "lucky number" within the matrix is defined by the specific condition of being the smallest number in its respective row and simultaneously the largest number in its respective column. The task is to identify all such numbers in the matrix and return them in any order.

Examples

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 and Intuition

1. Identify the minimum of each row.

   • Iterate through each row and find the minimum element.
   • Keep track of the index position where this minimum element occurs since this will be used to check the column conditions later.

2. Check if these minimums are the maximum in their respective columns.

   • For each minimum element identified in step 1, check its respective column to verify it's the largest value in that column.

3. Collect and return all such numbers that satisfy both conditions.

   • An array or list can be used to collect all the values which meet the criteria across the matrix.
   • If no such number is found, return an empty list.

The challenges to handle in this approach include efficiently searching each column multiple times and making sure that the operations stay within reasonable time limits, given the constraints. This method leverages the properties of numbers being distinct which simplifies the checking for maximum or minimum without having to consider ties. Each number’s unique property allows straightforward comparisons without additional checks for duplicate values.

Solutions

class Solution {
public:
    vector<int> findLuckyNumbers (vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
            
        int minMaxRowVal = INT_MIN;
        for (int row = 0; row < rows; row++) {
    
            int minRow = INT_MAX;
            for (int col = 0; col < cols; col++) {
                minRow = min(minRow, grid[row][col]);
            }
            minMaxRowVal = max(minMaxRowVal, minRow);
        }
            
        int maxMinColVal = INT_MAX;
        for (int col = 0; col < cols; col++) {
    
            int maxCol = INT_MIN;
            for (int row = 0; row < rows; row++) {
                maxCol = max(maxCol, grid[row][col]);
            }
            maxMinColVal = min(maxMinColVal, maxCol);
        }
            
        if (minMaxRowVal == maxMinColVal) {
            return {minMaxRowVal};
        }
            
        return {};
    }
};