Find Smallest Common Element in All Rows

medium matrix hash map counting

Problem

Given an m × 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.

Inputmat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]

Output5

5 is the smallest value that appears in all four rows.

mat (rows separated by ; values comma-separated, each row sorted)

def smallest_common_element(mat):
    rows = len(mat)
    count = {}
    for row in mat:
        for x in row:
            count[x] = count.get(x, 0) + 1
            if count[x] == rows:
                return x
    return -1

function smallestCommonElement(mat) {
  const rows = mat.length;
  const count = new Map();
  for (const row of mat) {
    for (const x of row) {
      const c = (count.get(x) || 0) + 1;
      count.set(x, c);
      if (c === rows) return x;
    }
  }
  return -1;
}

class Solution {
    public int smallestCommonElement(int[][] mat) {
        int rows = mat.length;
        Map<Integer, Integer> count = new HashMap<>();
        for (int[] row : mat) {
            for (int x : row) {
                int c = count.getOrDefault(x, 0) + 1;
                count.put(x, c);
                if (c == rows) return x;
            }
        }
        return -1;
    }
}

int smallestCommonElement(vector<vector<int>>& mat) {
    int rows = mat.size();
    unordered_map<int, int> count;
    for (auto& row : mat) {
        for (int x : row) {
            if (++count[x] == rows) return x;
        }
    }
    return -1;
}

Explanation

A value is common to all rows exactly when it appears once in each row. So we tally how many rows contain each value, and the first value to reach a count of rows is our answer.

We keep a hash map from value to count. Since every row is strictly increasing, a value can appear at most once per row, so incrementing its count by one as we scan a row genuinely means "seen in one more row."

We scan the matrix cell by cell, bumping each value's count. The moment a count hits rows, that value lives in every row, and because we sweep rows top to bottom in increasing order, the value we report is the smallest such common one. If no count ever reaches rows, we return -1.

Example: with four rows, the value 5 shows up in all of them, and its count reaches 4 before any other common value does, so the answer is 5.

This is a single pass over the grid, far simpler than intersecting rows pair by pair.

Time: O(m·n) Space: O(n)