Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1198.html

1198. Find Smallest Common Element in All Rows

Level

Medium

Description

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.

Solution

Maintain an index for each row of mat. Each time obtain an element from each row using the row’s current index. If the elements are all the same, then return the element. If the elements are different, then for the rows that have smaller elements, increase the corresponding indices by 1. If a row’s index exceeds the bound (which means the index is greater than or equal to mat’s number of columns), then there is no common element, so return -1.

  • class Solution {
    public int smallestCommonElement(int[][] mat) {
        if (mat == null || mat.length == 0 || mat[0].length == 0)
            return -1;
        int rows = mat.length, columns = mat[0].length;
        int[] indices = new int[rows];
        boolean flag = true;
        int curElement = 0;
        while (flag) {
            int count = 0;
            for (int i = 0; i < rows; i++) {
                int element = mat[i][indices[i]];
                curElement = Math.max(curElement, element);
            }
            for (int i = 0; i < rows; i++) {
                int element = mat[i][indices[i]];
                if (element == curElement)
                    count++;
                else if (element < curElement) {
                    indices[i]++;
                    if (indices[i] >= columns) {
                        flag = false;
                        break;
                    }
                }
            }
            if (count == rows)
                return curElement;
        }
        return -1;
    }
}

  • // OJ: https://leetcode.com/problems/find-smallest-common-element-in-all-rows/
// 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;
    }
};

  • class Solution:
    def smallestCommonElement(self, mat: List[List[int]]) -> int:
        counter = Counter()
        for row in mat:
            for num in row:
                counter[num] += 1
                if counter[num] == len(mat):
                    return num
        return -1

All Problems

All Solutions