# [1380. Lucky Numbers in a Matrix](https://leetcode.com/problems/lucky-numbers-in-a-matrix/description/)

# 1. Tóm tắt đề bài

Cho một ma trận $m * n$. Tìm tất cả các **số may mắn** xuất hiện trong ma trận.

*Số may mắn* là số bé nhất trong hàng của nó, và là số lớn nhất trong cột của nó.

##### Giới hạn

$1 \le m, n \le 50$
$1 \le matrix_{m, n} \le 10^5$
Các số trong ma trận **đôi một khác nhau**.

# 2. Tóm tắt lời giải

**Độ phức tạp dự tính: $O(m * n)$**

Với yêu cầu đề bài, không quá khó để thực hiện thuật toán trong $O(n * m)$. Ta tìm ra số lớn nhất từng cột, số bé nhất từng hàng, rồi duyệt xem những ô nào thỏa mãn điều kiện.

Bài này có một quan sát nho nhỏ mà có thể các bạn sẽ được yêu cầu tìm ra trong khi phỏng vấn:

- Nếu tồn tại một **lucky number** trong ma trận, thì số đó là ***duy nhất***.

Chứng minh khá đơn giản:

- Mỗi hàng/cột chỉ có một lucky number (dựa vào định nghĩa).
- Giả sử tồn tại 2 lucky number ở vị trí $(u, v)$ và $(s, t)$ (suy ra $u \neq s$ và $v \neq t$):
- Theo định nghĩa: $A_{u, v} > A_{s, v} > A_{s, t} > A_{u, t} > A_{u, v}$ -> vô lý.

# 3. Lời giải chi tiết

Dù có ứng dụng nhận xét hay không, complexity của bài này vẫn giữ nguyên. Vì vậy, mình sẽ chỉ gửi các bạn code mẫu để tham khảo nếu còn stuck:

- Ngây thơ (3 pass $m * n$): https://leetcode.com/problems/lucky-numbers-in-a-matrix/submissions/1325779753/
- Ứng dụng nhận xét (1 pass $m * n$): https://leetcode.com/problems/lucky-numbers-in-a-matrix/submissions/1325889680/

### Độ phức tạp thuật toán

Thời gian: $O(n * m)$

Bộ nhớ mở rộng: $O(n * m)$ nếu ngây thơ, $O(m + n)$ nếu nhận xét.

# 4. Kết luận & Gợi ý mở rộng

Tham gia Lowie's Leetcode Community: https://discord.gg/6bzRUnAZ6s

Các bài mở rộng:

[1958. Check if Move is Legal](https://leetcode.com/problems/check-if-move-is-legal/description/)

[2732. Find a Good Subset of the Matrix](https://leetcode.com/problems/find-a-good-subset-of-the-matrix/description/)