Find smallest common element in all rows

Array Hash Table Binary Search Matrix Counting

76.8% acceptance

Mar 31, 2026

606

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn smallest_common_element(mat: Vec<Vec<i32>>) -> i32 {
    // Count occurrences across rows
    let m = mat.len();
    let mut count = std::collections::HashMap::new();
    for row in &mat {
      for &val in row {
        *count.entry(val).or_insert(0usize) += 1;
      }
    }
    // Since each row is strictly increasing, each val appears at most once per row
    let mut result = -1;
    for (&val, &cnt) in &count {
      if cnt == m && (result == -1 || val < result) {
        result = val;
      }
    }
    result
  }
}