1198. Find Smallest Common Element in All Rows - Explanation

Description

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.

Example 1:

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:

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.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Count Elements

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)

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.

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

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)

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.

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

class Solution:
    def smallestCommonElement(self, mat: List[List[int]]) -> int:

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