# 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: