ให้ Matrix mat ที่ **ทุกแถวเรียงจากน้อยไปมาก (Non-decreasing)** หา **ตัวเลขที่เล็กที่สุดที่ปรากฏในทุกแถว** ถ้าไม่มีให้คืน -1
ตัวอย่าง
Matrix: [1, 2, 3, 4, 5] [2, 4, 5, 8, 10] [3, 5, 7, 9, 11] [1, 3, 5, 7, 9] Output: 5 (5 อยู่ในทุกแถว และเป็นตัวเล็กที่สุดที่ทำได้)
แนวทาง: Hash Map + เงื่อนไขความถี่ (Frequency Map with Row Tracking)
ใช้ Map นับความถี่ แต่มี **เทคนิคฉลาด** ไม่ต้องนับทุกแถวแยกกัน:
- Iterate ทุก Cell
mat[i][j] - เงื่อนไข:
if (m[mat[i][j]] + 1 == i + 1)แล้วค่อยเพิ่ม Count- หมายความ: ค่านี้เคยเจอในแถวที่ 0 ถึง i-1 ครบถ้วนแล้ว (เพราะแถวเรียง ไม่มีซ้ำในแถวเดียวกัน)
- ถ้าเจอในแถวเดียวกันซ้ำ (Impossible เพราะ Sorted) หรือข้ามแถว -> ไม่นับ
- หลังจบ ทำการหา Key ที่มี Value == จำนวนแถว (n) ตัวแรก (เพราะ Map เรียง Key อัตโนมัติ)
ตัวอย่างโค้ด C++
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int smallestCommonElement(vector<vector<int>>& mat) {
map<int, int> m; // Map เรียง Key อัตโนมัติ (Red-Black Tree)
int n = mat.size();
int cols = n ? mat[0].size() : 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < cols; j++) {
int val = mat[i][j];
// เทคนิคสำคัญ: นับเฉพาะตอนเจอในแถวถัดไปต่อเนื่อง
if (m[val] + 1 == i + 1) {
m[val]++;
}
}
}
// Map เรียง Key น้อยไปมาก -> ตัวแรกที่ count == n คือคำตอบ
for (auto& [key, cnt] : m) {
if (cnt == n) return key;
}
return -1;
}
};
Input / Output
Input: [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]] Output: 5
ความซับซ้อน (Complexity)
- Time: O(N * M log K) — N แถว, M คอลัมน์, K ค่าที่แตกต่าง (Map Insert log K)
- Space: O(K) — เก็บค่าที่ไม่ซ้ำใน Map
วิธีอื่น (Alternative)
เพราะแถวเรียงแล้ว สามารถใช้ **3 Pointers / Binary Search** ได้ O(N log M) หรือ **Min-Heap** ได้ O(N M log N) วิธี Map นี้เขียนง่าย กระชับ และพอสำหรับ Constraints ปกติครับ
