Given a 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
Constraints:
1 <= mat.length, mat[i].length <= 500
1 <= mat[i][j] <= 10^4
mat[i]
is sorted in strictly increasing order.struct Solution;
impl Solution {
fn smallest_common_element(mat: Vec<Vec<i32>>) -> i32 {
let mut count: Vec<usize> = vec![0; 10001];
let n = mat.len();
let m = mat[0].len();
for i in 0..n {
for j in 0..m {
count[mat[i][j] as usize] += 1;
}
}
for j in 0..m {
let x = mat[0][j];
if count[x as usize] == n {
return x;
}
}
-1
}
}
#[test]
fn test() {
let mat = vec_vec_i32![
[1, 2, 3, 4, 5],
[2, 4, 5, 8, 10],
[3, 5, 7, 9, 11],
[1, 3, 5, 7, 9]
];
let res = 5;
assert_eq!(Solution::smallest_common_element(mat), res);
}