1143. Find Smallest Common Element in All Rows

• Difficulty: Medium

• Topics: Hash Table, Binary Search

• Similar Questions:

Problem:

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

If there is no common element, return -1.

Example 1:

Input: mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]
Output: 5

Constraints:

• 1 <= mat.length, mat[i].length <= 500
• 1 <= mat[i][j] <= 10^4
• mat[i] is sorted in increasing order.

Solutions:

class Solution {
public:
    int smallestCommonElement(vector<vector<int>>& mat) {
        int m = mat.size();
        if (m == 0) return -1;
        int n = mat[0].size();
        if (n == 0) return -1;

        for (auto& num : mat[0]) {
            bool found = true;
            for (int i = 1; i < m; ++i) {
                if (find(mat[i].begin(), mat[i].end(), num) == mat[i].end()) {
                    found = false;
                    break;
                }
            }
            if (found) return num;
        }

        return -1;

    }
};