[Coderust] Find Smallest Common Element in All Rows

 

 

Problem

 

 

 

---

 

Solution

 

Look at the first number on the first row.

Then perform binary search (time complexity = log N) to find that element in the rest of the matrix.

If the loop ended before currRow is updated to the row length of matrix, the code did not find the number in the rest of the rows. Move onto the next number in the first row and repeat.

 

 

Time Complexity

 

O(M+N) maximum

 

Space Complexity

 

O(1)

 

 

class Solution:
    def smallestCommonElement(self, mat):
        r = len(mat)
        c = len(mat[0])
        for j in range(c):
            currMin = mat[0][j]
            currRow = 0
            for i in range(1, r):
                currRow += 1
                if self.binarySearch(mat[i], currMin):
                    continue
                else:
                    break
            if currRow == r:
                return currMin
        return -1


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