[LeetCode] Find Smallest Common Element in All Rows

1198. Find Smallest Common Element in All Rows

Given a matrix mat where every row is sorted in strictly increasing order, return the smallest common element in all rows.

If there is no common element, return -1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
int smallestCommonElement(vector<vector<int>>& mat) {
set<int> commonElement(mat[0].begin(), mat[0].end());

for(int i = 1; i < mat.size(); i++) {
unordered_set<int> removeElement;
auto element = commonElement.begin();
for(int j = 0; j < mat[i].size() && element != commonElement.end(); j++) {
if(*element < mat[i][j]) {
while(element != commonElement.end() && *element < mat[i][j]) {
removeElement.insert(*element);
element = next(element);
}
}
if(element != commonElement.end() && *element == mat[i][j]) {
element = next(element);
}
}
for(auto& remove : removeElement) {
commonElement.erase(remove);
}
}

return commonElement.empty() ? -1 : *commonElement.begin();
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2021/03/22/PS/LeetCode/find-smallest-common-element-in-all-rows/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.