1198. Find Smallest Common Element in All Rows

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.

Rust Solution

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);
}

Having problems with this solution? Click here to submit an issue on github.