1198

1198. Find Smallest Common Element in All Rows (Medium)

Given an m x n 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.

 

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

Example 2:

Input: mat = [[1,2,3],[2,3,4],[2,3,5]]
Output: 2

 

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 500
• 1 <= mat[i][j] <= 104
• mat[i] is sorted in strictly increasing order.

Companies:
Qualtrics, Intel, Walmart Labs

Related Topics:
Array, Hash Table, Binary Search, Matrix, Counting

Solution 1.

// OJ: https://leetcode.com/problems/find-smallest-common-element-in-all-rows/
// Author: github.com/lzl124631x
// Time: O(MN)
// Space: O(M)
class Solution {
public:
    int smallestCommonElement(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size();
        vector<int> index(M);
        for (int j = 0; j < N; ++j) {
            int n = A[0][j], i = 1;
            for (; i < M; ++i) {
                while (index[i] < N && A[i][index[i]] < n) ++index[i];
                if (index[i] == N) return -1;
                if (A[i][index[i]] != n) break;
            }
            if (i == M) return n;
        }
        return -1;
    }
};

Solution 2. Binary Search

// OJ: https://leetcode.com/problems/find-smallest-common-element-in-all-rows/
// Author: github.com/lzl124631x
// Time: O(NMlogN)
// Space: O(1)
class Solution {
public:
    int smallestCommonElement(vector<vector<int>>& A) {
        int M = A.size(), N = A[0].size();
        for (int j = 0; j < N; ++j) {
            int n = A[0][j], i = 1;
            for (; i < M; ++i) {
                int k = lower_bound(begin(A[i]), end(A[i]), n) - begin(A[i]);
                if (k > N) return -1;
                if (A[i][k] != n) break;
            }
            if (i == M) return n;
        }
        return -1;
    }
};