Problem

Given an m x n matrix mat where every row is sorted in strictly increasing order, return thesmallest common element in all rows.

If there is no common element, return -1.

Examples

Example 1:

1
2

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:

1
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] <= 10^4
  • mat[i] is sorted in strictly increasing order.

Solution

Method 1 – Counting Occurrences

Intuition

Since each row is sorted and contains only unique elements, we can count the occurrences of each number across all rows. The smallest number that appears in every row is the answer.

Approach

  1. Initialize a hash map (or array if values are bounded) to count occurrences of each number.
  2. For each row, increment the count for each number.
  3. After processing all rows, iterate through the keys in increasing order and return the first number whose count equals the number of rows.
  4. If no such number exists, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int smallestCommonElement(vector<vector<int>>& mat) {
        unordered_map<int, int> cnt;
        int m = mat.size();
        for (auto& row : mat) for (int x : row) cnt[x]++;
        int ans = INT_MAX;
        for (auto& [k, v] : cnt) if (v == m) ans = min(ans, k);
        return ans == INT_MAX ? -1 : ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func smallestCommonElement(mat [][]int) int {
    cnt := map[int]int{}
    m := len(mat)
    for _, row := range mat {
        for _, x := range row {
            cnt[x]++
        }
    }
    ans := 1<<31 - 1
    for k, v := range cnt {
        if v == m && k < ans {
            ans = k
        }
    }
    if ans == 1<<31-1 {
        return -1
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int smallestCommonElement(int[][] mat) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int m = mat.length;
        for (int[] row : mat) for (int x : row) cnt.put(x, cnt.getOrDefault(x, 0) + 1);
        int ans = Integer.MAX_VALUE;
        for (var e : cnt.entrySet()) if (e.getValue() == m) ans = Math.min(ans, e.getKey());
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}
1
2
3
4
5
6
7
8

class Solution {
    fun smallestCommonElement(mat: Array<IntArray>): Int {
        val cnt = mutableMapOf<Int, Int>()
        val m = mat.size
        for (row in mat) for (x in row) cnt[x] = cnt.getOrDefault(x, 0) + 1
        return cnt.filter { it.value == m }.keys.minOrNull() ?: -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def smallestCommonElement(self, mat: list[list[int]]) -> int:
        from collections import Counter
        m = len(mat)
        cnt = Counter()
        for row in mat:
            cnt.update(row)
        for x in sorted(cnt):
            if cnt[x] == m:
                return x
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn smallest_common_element(mat: Vec<Vec<i32>>) -> i32 {
        use std::collections::HashMap;
        let m = mat.len();
        let mut cnt = HashMap::new();
        for row in &mat {
            for &x in row {
                *cnt.entry(x).or_insert(0) += 1;
            }
        }
        let mut ans = i32::MAX;
        for (&k, &v) in &cnt {
            if v == m && k < ans {
                ans = k;
            }
        }
        if ans == i32::MAX { -1 } else { ans }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    smallestCommonElement(mat: number[][]): number {
        const cnt: Record<number, number> = {};
        const m = mat.length;
        for (const row of mat) for (const x of row) cnt[x] = (cnt[x] ?? 0) + 1;
        let ans = Infinity;
        for (const k in cnt) if (cnt[k] === m && +k < ans) ans = +k;
        return ans === Infinity ? -1 : ans;
    }
}

Complexity

  • ⏰ Time complexity: O(mn), where m is the number of rows and n is the number of columns, since we scan all elements.
  • 🧺 Space complexity: O(n), for the count map (number of unique elements).