Solutions

1. Count Elements

Intuition

An element is common to all rows if it appears exactly n times across the matrix (once per row, since rows are sorted). We can count occurrences of each element and then scan from smallest to largest to find the first element with count equal to n. This works because each row contains distinct elements in sorted order.

Algorithm

Create a count array of size 10001 (given the constraint on element values).
Iterate through all elements in the matrix and increment their counts.
Scan from 1 to 10000 and return the first element with count equal to n.
If no such element exists, return -1.

class Solution:
    def smallestCommonElement(self, mat: List[List[int]]) -> int:
        count = [0] * 10001
        n, m = len(mat), len(mat[0])
        
        for i in range(n):
            for j in range(m):
                count[mat[i][j]] += 1
        
        for k in range(1, 10001):
            if count[k] == n:
                return k
        
        return -1

1. Count Elements (Improved)

Intuition

We can improve the average time complexity if we count elements column-by-column. This way, smaller elements will be counted first, and we can exit as soon as we get to an element that repeats n times.

Algorithm

Create a count array of size 10001.
Iterate column by column (outer loop), then row by row (inner loop).
For each element, increment its count.
If the count reaches n, return that element immediately.
If no common element is found after processing all elements, return -1.

class Solution:
    def smallestCommonElement(self, mat: List[List[int]]) -> int:
        count = [0] * 10001
        n, m = len(mat), len(mat[0])
        
        for j in range(m):
            for i in range(n):
                count[mat[i][j]] += 1
                if count[mat[i][j]] == n:
                    return mat[i][j]
        
        return -1

Handling Duplicates

If elements are in non-decreasing order, we'll need to modify these solutions to properly handle duplicates. For example, we return 4 (initial solution) and 7 (improved solution) instead of 5 for this test case:

[[1,2,3,4,5],[5,7,7,7,7],[5,7,7,7,7],[1,2,4,4,5],[1,2,4,4,5]]

It's easy to modify these solutions to handle duplicates. Since elements in a row are sorted, we can skip the current element if it's equal to the previous one.

Time & Space Complexity

Time complexity: $O(nm)$
Space complexity:
- Constrained problem: $O(10000) = O(1)$ constant space.
- Unconstrained problem: $O(k)$ , where $k$ is the number of unique elements.

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

2. Binary Search

Intuition

Since each row is sorted, we can use binary search to check if an element exists in a row. We iterate through the first row (which is already sorted from smallest to largest) and for each element, we binary search for it in all other rows. The first element found in all rows is our answer.

Algorithm

Iterate through each element in the first row (from smallest to largest).
For each element, use binary search to check if it exists in every other row.
If the element is found in all rows, return it.
If no common element is found, return -1.

class Solution:
    def smallestCommonElement(self, mat: List[List[int]]) -> int:
        n, m = len(mat), len(mat[0])
        
        for j in range(m):
            found = True
            i = 1
            while i < n and found:
                found = self.binarySearch(mat[i], mat[0][j]) >= 0
                i += 1
            
            if found:
                return mat[0][j]
        
        return -1
    

    def binarySearch(self, arr, target):
        left, right = 0, len(arr) - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] == target:
                return mid
            elif arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -1

2. Binary Search (Improved)

Intuition

In the solution above, we always search the entire row. We can improve the average time complexity if we start the next search from the position returned by the previous search. We can also return -1 if all elements in the row are smaller than value we searched for.

Algorithm

Maintain a pos array to track search starting points for each row.
For each element in the first row:
- Binary search in each other row, starting from the stored position.
- If not found, update the position to where it would be inserted.
- If the position exceeds row length, return -1 (no common element possible).
If an element is found in all rows, return it.
If no common element is found, return -1.

class Solution:
    def smallestCommonElement(self, mat: List[List[int]]) -> int:
        n, m = len(mat), len(mat[0])
        pos = [0] * n
        
        for j in range(m):
            found = True
            i = 1
            while i < n and found:
                pos[i] = self.binarySearch(mat[i], pos[i], m, mat[0][j])
                if pos[i] < 0:
                    found = False
                    pos[i] = -pos[i] - 1
                    if pos[i] >= m:
                        return -1
                i += 1
            
            if found:
                return mat[0][j]
        
        return -1
    

    def binarySearch(self, arr, fromIndex, toIndex, target):
        left, right = fromIndex, toIndex - 1
        while left <= right:
            mid = (left + right) // 2
            if arr[mid] == target:
                return mid
            elif arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return -(left + 1)

Handling Duplicates

Since we search for an element in each row, this approach works correctly if there are duplicates.

Time & Space Complexity

Time complexity: $O(m n \log m)$
Space complexity:
- Original Solution: $O(1)$ constant space.
- Improved Solution: $O(n)$

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

3. Row Positions

Intuition

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.

Algorithm

Initialize a pos array with zeros and set curMax = 0 and cnt = 0.
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.
Repeat until a common element is found or determined impossible.

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

Handling Duplicates

Since we take one element from each row, this approach works correctly if there are duplicates.

Time & Space Complexity

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

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

Common Pitfalls

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.