# 1198. Find Smallest Common Element in All Rows

Given a matrix mat where every row is sorted in 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

# Solution

Approach 1: deduplicate each row and count frequency, then go through the first row to find frequency == num of rows. For M by N matrix, time: O(MN), space: O(MN).

Approach 2: take every element in the first row, and do binary search in each of the subsequent rows. Time: O(MNlogN), space: O(1).

Approach 3: use a heap to store all pointers to all rows, and keep the max value of the heap; if max_val == heap's min val, all pointers point to the same value. Time: O(MNlogM), space: O(M).

# Code (Python)

Approach 3:

    def smallestCommonElement(self, mat: List[List[int]]) -> int:
        if not mat or not mat[0]:
            return -1
        
        # use a heap to store all pointers to all rows
        # also keep the max value of the heap; if max_val == heap's min val, all pointers point to the same value
        # for M * N matrix, time: O(MNlogM), space: O(M)
        heap = []
        heap_max_val = -float('inf')
        for i, array in enumerate(mat):
            heapq.heappush(heap, (array[0], 0, i))
            heap_max_val = max(heap_max_val, array[0])

        while len(heap) == len(mat) and heap_max_val != heap[0][0]:
            min_val, index, array_index = heapq.heappop(heap)
            if index + 1 < len(mat[0]):
                heapq.heappush(heap, (mat[array_index][index+1], index + 1, array_index))
                heap_max_val = max(heap_max_val, mat[array_index][index+1])
                if heap_max_val == heap[0][0]:
                    return heap[0][0]
            else:
                return -1
        
        return -1 if len(heap) != len(mat) or not heap else heap[0][0]

# Code (C++)

Approach 1:

Approach 2: