Find Smallest Common Element in All Rows

How it works

We can use a two-pointer style approach across all rows. We maintain a pos pointer for each row and track the current maximum value seen. When we find a value smaller than the current max, we advance that row's pointer. If all rows have the same value at their current positions, we found our answer. If any row's pointer goes out of bounds, no common element exists.

Steps

1. Initialize a pos array with zeros and set curMax = 0 and cnt = 0.
2. Loop through each row:
   • Advance the position while the current element is less than curMax.
   • If position exceeds row bounds, return -1.
   • If the element differs from curMax, reset cnt = 1 and update curMax.
   • Otherwise, increment cnt. If cnt == n, return curMax.
3. Repeat until a common element is found or determined impossible.

Complexity

• Time complexity: O(nm)
• Space complexity: O(n)

where m is the number of rows and n is the number of columns

Things to watch for

Not Handling Duplicates in Non-Decreasing Arrays

The problem states rows are sorted in strictly increasing order, but if the input contains non-decreasing order (with duplicates), the counting approach breaks. An element appearing twice in one row would be counted twice, potentially reaching the row count n without actually being present in all rows.

Returning the First Element Found Instead of the Smallest

When iterating column-by-column or using binary search, ensure you process elements in order from smallest to largest. If you iterate row-by-row first, you might find a common element that is not the smallest one.

Off-by-One Errors in Binary Search Bounds

When using the improved binary search with position tracking, be careful with the boundary conditions. Returning -1 too early when pos[i] >= m is correct, but forgetting to update positions properly after a failed search can cause infinite loops or missed elements.

from typing import List

class Solution:
    def smallestCommonElement(self, mat: List[List[int]]) -> int:
        n, m = len(mat), len(mat[0])
        pos = [0] * n
        cur_max, cnt = 0, 0

        while True:
            for i in range(n):
                while pos[i] < m and mat[i][pos[i]] < cur_max:
                    pos[i] += 1
                if pos[i] >= m:
                    return -1
                if mat[i][pos[i]] != cur_max:
                    cnt = 1
                    cur_max = mat[i][pos[i]]
                else:
                    cnt += 1
                    if cnt == n:
                        return cur_max

class Solution {
public:
    int smallestCommonElement(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        int cur_max = 0, cnt = 0;
        vector<int> pos(n);
        while (true) {
            for (int i = 0; i < n; ++i) {
                while (pos[i] < m && mat[i][pos[i]] < cur_max) {
                    ++pos[i];
                }
                if (pos[i] >= m) {
                    return -1;
                }
                if (cur_max != mat[i][pos[i]]) {
                    cnt = 1;
                    cur_max = mat[i][pos[i]];
                } else if (++cnt == n) {
                    return cur_max;
                }
            }
        }
        return -1;
    }
};