# Lucky Numbers in a Matrix
**Difficulty:** EASY
[External](https://leetcode.com/problems/lucky-numbers-in-a-matrix)
Canonical: https://scaleengineer.com/dsa/problems/lucky-numbers-in-a-matrix
**Data structures:** Array, Matrix
**Companies:** [Cisco](https://scaleengineer.com/companies/cisco)
---
## Problem
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.

# Approaches
## Brute Force Iteration
This approach iterates through every single element of the matrix. For each element, it performs two checks: first, whether it's the minimum in its row, and second, whether it's the maximum in its column. If both conditions are met, the element is a "lucky number" and is added to the result list.
**Time:** O(m * n * (m + n)). For each of the `m*n` elements, we scan its row (`n` elements) and potentially its column (`m` elements). · **Space:** O(1) auxiliary space, not counting the space for the output list.
**Pros:** Simple to understand and implement.; Requires no extra data structures.
**Cons:** Highly inefficient, especially for large matrices, due to redundant computations.
### Explanation
The algorithm involves a nested loop to visit each cell `(i, j)` of the matrix. For each cell `matrix[i][j]`, we first assume it's a lucky number. We then iterate through its entire row `i` to check if any other element `matrix[i][k]` is smaller than `matrix[i][j]`. If we find one, `matrix[i][j]` is not the row minimum, so it can't be a lucky number. We move to the next element in the matrix. If it is indeed the row minimum, we proceed to check its column `j`. We iterate through the entire column `j` to see if any other element `matrix[k][j]` is larger than `matrix[i][j]`. If we find one, it's not the column maximum and thus not a lucky number. Only if an element passes both the row minimum and column maximum checks is it added to the final list of lucky numbers.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> luckyNumbers (int[][] matrix) {
        List<Integer> luckyNumbers = new ArrayList<>();
        int m = matrix.length;
        int n = matrix[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int candidate = matrix[i][j];
                boolean isMinInRow = true;
                for (int k = 0; k < n; k++) {
                    if (matrix[i][k] < candidate) {
                        isMinInRow = false;
                        break;
                    }
                }

                if (isMinInRow) {
                    boolean isMaxInCol = true;
                    for (int k = 0; k < m; k++) {
                        if (matrix[k][j] > candidate) {
                            isMaxInCol = false;
                            break;
                        }
                    }
                    if (isMaxInCol) {
                        luckyNumbers.add(candidate);
                    }
                }
            }
        }
        return luckyNumbers;
    }
}
```
### Algorithm
- Initialize an empty list `luckyNumbers`.
- Iterate through each row `i` from 0 to `m-1`.
-   Iterate through each column `j` from 0 to `n-1`.
-     Let `candidate = matrix[i][j]`.
-     Check if `candidate` is the minimum in row `i`.
       -   Set a flag `isMinInRow = true`.
       -   Iterate `k` from 0 to `n-1`. If `matrix[i][k] < candidate`, set `isMinInRow = false` and break.
-     If `isMinInRow` is true, check if `candidate` is the maximum in column `j`.
       -   Set a flag `isMaxInCol = true`.
       -   Iterate `k` from 0 to `m-1`. If `matrix[k][j] > candidate`, set `isMaxInCol = false` and break.
-     If `isMaxInCol` is also true, add `candidate` to `luckyNumbers`.
- Return `luckyNumbers`.

## Optimized Row-wise Check
This approach improves upon the brute-force method by reducing redundant checks. Instead of checking every element, we first identify the minimum element in each row. Only these row-minimums are candidates for being lucky numbers. Then, for each of these candidates, we check if it is the maximum in its respective column.
**Time:** O(m * (n + m)). For each of the `m` rows, we spend `O(n)` to find the minimum and `O(m)` to check the column. · **Space:** O(1) auxiliary space, not counting the space for the output list.
**Pros:** More efficient than the pure brute-force approach.; Still maintains low space complexity.
**Cons:** Can still be slow if the number of rows (`m`) is large, as the complexity is `O(m*n + m^2)`.
### Explanation
The algorithm iterates through each row of the matrix one by one. For each row `i`, it finds the minimum value `minVal` and its column index `minIndex`. This is done with a single scan of the row. Once the row minimum `minVal` is found, it is a potential lucky number. The first condition (minimum in its row) is already satisfied. The next step is to verify the second condition: whether `minVal` is the maximum element in its column `minIndex`. To do this, we iterate through all elements in column `minIndex` and compare them with `minVal`. If no element in the column is greater than `minVal`, it satisfies the second condition and is added to the result list. This process is repeated for all rows.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> luckyNumbers (int[][] matrix) {
        List<Integer> luckyNumbers = new ArrayList<>();
        int m = matrix.length;
        int n = matrix[0].length;

        for (int i = 0; i < m; i++) {
            // Find the minimum element in the current row
            int minVal = matrix[i][0];
            int minIndex = 0;
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] < minVal) {
                    minVal = matrix[i][j];
                    minIndex = j;
                }
            }

            // Check if this element is the maximum in its column
            boolean isMaxInCol = true;
            for (int k = 0; k < m; k++) {
                if (matrix[k][minIndex] > minVal) {
                    isMaxInCol = false;
                    break;
                }
            }

            if (isMaxInCol) {
                luckyNumbers.add(minVal);
            }
        }
        return luckyNumbers;
    }
}
```
### Algorithm
- Initialize an empty list `luckyNumbers`.
- Iterate through each row `i` from 0 to `m-1`.
-   Find the minimum value `minVal` and its column index `minIndex` in the current row `i`.
-   Assume `minVal` is a lucky number (i.e., it's the maximum in its column). Let `isMaxInCol = true`.
-   Iterate through each row `k` from 0 to `m-1` to check column `minIndex`.
-     If `matrix[k][minIndex] > minVal`, then `minVal` is not the maximum in its column. Set `isMaxInCol = false` and break the inner loop.
-   If `isMaxInCol` remains true after checking the entire column, add `minVal` to the `luckyNumbers` list.
- Return `luckyNumbers`.

## Two-Pass Pre-computation
This is the most efficient approach. It avoids nested checks by pre-calculating all row minimums and all column maximums in two separate passes. A number is a lucky number if and only if it is present in both the list of row minimums and the list of column maximums.
**Time:** O(m * n). Populating `rowMins` takes `O(m*n)`. Populating `colMaxs` takes `O(m*n)`. Finding the intersection takes `O(m + n)`. The dominant term is `O(m*n)`. · **Space:** O(m + n). We use an array of size `m` for row minimums, an array of size `n` for column maximums, and a hash set of size up to `m`.
**Pros:** Most efficient time complexity as it avoids redundant computations by processing rows and columns independently first.
**Cons:** Uses extra space proportional to the dimensions of the matrix.
### Explanation
The algorithm uses two auxiliary arrays: `rowMins` to store the minimum value of each row, and `colMaxs` to store the maximum value of each column. 
**First Pass:** Iterate through the matrix to populate `rowMins`. For each row `i`, find its minimum element and store it in `rowMins[i]`. 
**Second Pass:** Iterate through the matrix again (or iterate column by column) to populate `colMaxs`. For each column `j`, find its maximum element and store it in `colMaxs[j]`. 
**Final Check:** After pre-computation, we have all the candidates. A number `x` is a lucky number if it's a minimum in some row `i` (`x == rowMins[i]`) and a maximum in some column `j` (`x == colMaxs[j]`). Since all matrix elements are distinct, we can simply find the intersection of the values in `rowMins` and `colMaxs`. To find the intersection efficiently, we can add all row minimums to a `HashSet` for `O(1)` average time lookups. Then, we iterate through the column maximums and check if each one exists in the set. If it does, it's a lucky number.

```java
import java.util.ArrayList;
import java.util.List;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public List<Integer> luckyNumbers (int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        int[] rowMins = new int[m];
        for (int i = 0; i < m; i++) {
            int minVal = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                minVal = Math.min(minVal, matrix[i][j]);
            }
            rowMins[i] = minVal;
        }

        int[] colMaxs = new int[n];
        for (int j = 0; j < n; j++) {
            int maxVal = Integer.MIN_VALUE;
            for (int i = 0; i < m; i++) {
                maxVal = Math.max(maxVal, matrix[i][j]);
            }
            colMaxs[j] = maxVal;
        }

        List<Integer> luckyNumbers = new ArrayList<>();
        Set<Integer> rowMinsSet = new HashSet<>();
        for (int minVal : rowMins) {
            rowMinsSet.add(minVal);
        }

        for (int maxVal : colMaxs) {
            if (rowMinsSet.contains(maxVal)) {
                luckyNumbers.add(maxVal);
            }
        }

        return luckyNumbers;
    }
}
```
### Algorithm
- Get matrix dimensions `m` and `n`.
- Create an array `rowMins` of size `m`.
- Iterate `i` from 0 to `m-1`:
   -   Find the minimum value in `matrix[i]` and store it in `rowMins[i]`.
- Create an array `colMaxs` of size `n`.
- Iterate `j` from 0 to `n-1`:
   -   Find the maximum value in column `j` of the matrix and store it in `colMaxs[j]`.
- Initialize an empty list `luckyNumbers`.
- Create a `HashSet<Integer>` and add all elements from `rowMins` to it.
- Iterate through each value `maxVal` in `colMaxs`:
   -   If the set contains `maxVal`, add `maxVal` to `luckyNumbers`.
- Return `luckyNumbers`.

# Solutions
### Java

```java
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, 1 << 30);
    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(rows[i]);
        }
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[][]} matrix * @return {number[]} */ var luckyNumbers = function ( matrix ) { const m = matrix . length ; const n = matrix [ 0 ]. length ; const rows = new Array ( m ). fill ( 1 << 30 ); const cols = new Array ( n ). fill ( 0 ); for ( let i = 0 ; i < m ; ++ i ) { for ( let j = 0 ; j < n ; j ++ ) { rows [ i ] = Math . min ( rows [ i ], matrix [ i ][ j ]); cols [ j ] = Math . max ( cols [ j ], matrix [ i ][ j ]); } } const ans = []; for ( let i = 0 ; i < m ; ++ i ) { for ( let j = 0 ; j < n ; j ++ ) { if ( rows [ i ] === cols [ j ]) { ans . push ( rows [ i ]); } } } return ans ; };
```

### CPP

```cpp
class Solution {
public:
  vector<int> luckyNumbers(vector<vector<int>> &matrix) {
    int m = matrix.size(), n = matrix[0].size();
    int rows[m];
    int cols[n];
    memset(rows, 0x3f, sizeof(rows));
    memset(cols, 0, sizeof(cols));
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        rows[i] = min(rows[i], matrix[i][j]);
        cols[j] = max(cols[j], matrix[i][j]);
      }
    }
    vector<int> ans;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (rows[i] == cols[j]) {
          ans.push_back(rows[i]);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
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)

```