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(); } };
|