Skip to content

1198. Find Smallest Common Element in All Rows 👍

  • Time: $O(mn)$
  • Space: $O(10000) = O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
 public:
  int smallestCommonElement(vector<vector<int>>& mat) {
    constexpr int kMax = 10000;
    vector<int> count(kMax + 1);

    for (const vector<int>& row : mat)
      for (const int a : row)
        if (++count[a] == mat.size())
          return a;

    return -1;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
  public int smallestCommonElement(int[][] mat) {
    final int kMax = 10000;
    int[] count = new int[kMax + 1];

    for (int[] row : mat)
      for (final int a : row)
        if (++count[a] == mat.length)
          return a;

    return -1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def smallestCommonElement(self, mat: List[List[int]]) -> int:
    kMax = 10000
    count = [0] * (kMax + 1)

    for row in mat:
      for a in row:
        count[a] += 1
        if count[a] == len(mat):
          return a

    return -1