224. Lucky Cells
A treasure map is a grid grid of different numbers. A cell is lucky when its value is the smallest value in its own row and, at the same time, the largest value in its own column. In a grid of distinct numbers it is possible that no cell is lucky.
Return the values of all lucky cells, listed in row-major order (row by row, left to right). If there is no lucky cell, return an empty array. To keep the answer well defined, a cell counts as lucky as soon as no other cell in its row is smaller and no other cell in its column is larger.
Example 1
- Input:
- grid = [[10,4,12],[11,6,15],[8,3,9]]
- Output:
- [6]
- Explanation:
The row minima are 4, 6 and 3. Only 6 is also the largest in its column (column 1 holds 4, 6, 3), so the answer is [6].
Example 2
- Input:
- grid = [[1,10],[2,20]]
- Output:
- [2]
- Explanation:
The row minima are 1 and 2. The value 1 is not the column maximum (2 is bigger), but 2 is the maximum of column 0, so the answer is [2].
Example 3
- Input:
- grid = [[7,4,9],[2,8,5],[6,3,1]]
- Output:
- []
- Explanation:
The row minima 4, 2 and 1 are each beaten by a larger value in their column, so no cell is lucky and the answer is empty.
Constraints
1 ≤ grid.length, grid[0].length ≤ 50
1 ≤ grid[i][j] ≤ 105
All the numbers in the grid are distinct.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(m × n)
- Space
- O(m + n)