Question

1198. Find Smallest Common Element in All Rows

中文文档

Description

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.

Solutions

Solution 1: Counting

We use an array $cnt$ of length $10001$ to count the frequency of each number. We sequentially traverse each number in the matrix and increment its frequency. When the frequency of a number equals the number of rows in the matrix, it means that this number appears in each row, and thus it is the smallest common element. We return this number.

If we do not find the smallest common element after the traversal, we return $-1$.

The time complexity is $O(m \times n)$, and the space complexity is $O(10^4)$. Here, $m$ and $n$ are the number of rows and columns in the matrix, respectively.

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

class Solution {
  public int smallestCommonElement(int[][] mat) {
    int[] cnt = new int[10001];
    for (var row : mat) {
      for (int x : row) {
        if (++cnt[x] == mat.length) {
          return x;
        }
      }
    }
    return -1;
  }
}

class Solution {
public:
  int smallestCommonElement(vector<vector<int>>& mat) {
    int cnt[10001]{};
    for (auto& row : mat) {
      for (int x : row) {
        if (++cnt[x] == mat.size()) {
          return x;
        }
      }
    }
    return -1;
  }
};

func smallestCommonElement(mat [][]int) int {
  cnt := [10001]int{}
  for _, row := range mat {
    for _, x := range row {
      cnt[x]++
      if cnt[x] == len(mat) {
        return x
      }
    }
  }
  return -1
}

function smallestCommonElement(mat: number[][]): number {
  const cnt: number[] = new Array(10001).fill(0);
  for (const row of mat) {
    for (const x of row) {
      if (++cnt[x] == mat.length) {
        return x;
      }
    }
  }
  return -1;
}