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.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|