Find Smallest Common Element in All Rows Solutions in C++

/// Source : https://leetcode.com/problems/find-smallest-common-element-in-all-rows/
/// Author : liuyubobobo
/// Time   : 2019-09-21

#include <iostream>
#include <vector>
#include <set>

using namespace std;


/// Using TreeSet
/// Time Complexity: O(m * n * log m * n)
/// Space Complexity: O(m * n)
class Solution {
public:
    int smallestCommonElement(vector<vector<int>>& mat) {

        set<int> set1;
        for(int e: mat[0]) set1.insert(e);

        for(int i = 1; i < mat.size(); i ++){

            set<int> set2;
            for(int e: mat[i]) if(set1.count(e)) set2.insert(e);
            set1 = set2;
        }

        return set1.size() ? *set1.begin() : -1;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/find-smallest-common-element-in-all-rows/
/// Author : liuyubobobo
/// Time   : 2019-09-21

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;


/// Using HashSet
/// Time Complexity: O(m * n)
/// Space Complexity: O(m * n)
class Solution {
public:
    int smallestCommonElement(vector<vector<int>>& mat) {

        unordered_set<int> set1;
        for(int e: mat[0]) set1.insert(e);

        for(int i = 1; i < mat.size(); i ++){

            unordered_set<int> set2;
            for(int e: mat[i]) if(set1.count(e)) set2.insert(e);
            set1 = set2;
        }

        return set1.size() ? *min_element(set1.begin(), set1.end()) : -1;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/find-smallest-common-element-in-all-rows/
/// Author : liuyubobobo
/// Time   : 2019-09-21

#include <iostream>
#include <vector>
#include <set>

using namespace std;


/// Brute Force Count
/// Time Complexity: O(m * n)
/// Space Complexity: O(max(value))
class Solution {
public:
    int smallestCommonElement(vector<vector<int>>& mat) {

        vector<int> cnt(10001, 0);
        for(int i = 0; i < mat.size(); i ++)
            for(int j = 0; j < mat[i].size(); j ++){
                cnt[mat[i][j]] ++;
                if(cnt[mat[i][j]] == mat.size()) return mat[i][j];
            }
        return -1;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/find-smallest-common-element-in-all-rows/
/// Author : liuyubobobo
/// Time   : 2019-09-21

#include <iostream>
#include <vector>
#include <set>

using namespace std;


/// Binary Search
/// Time Complexity: O(m * n * log m * n)
/// Space Complexity: O(1)
class Solution {
public:
    int smallestCommonElement(vector<vector<int>>& mat) {

        for(int e: mat[0]){

            int i;
            for(i = 1; i < mat.size(); i ++){
                vector<int>::const_iterator iter = lower_bound(mat[i].begin(), mat[i].end(), e);
                if(iter == mat[i].end() || *iter != e) break;
            }

            if(i == mat.size()) return e;
        }
        return -1;
    }
};


int main() {

    vector<vector<int>> mat1 = {
            {1,2,3,4,5},{2,4,5,8,10},{3,5,7,9,11},{1,3,5,7,9}
    };
    cout << Solution().smallestCommonElement(mat1) << endl;

    return 0;
}