Find Smallest Common Element in All Rows

Patrick Leaton
Published: Nov. 8, 2021, 8:05 p.m.
Problem 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.

 

The description was taken from https://leetcode.com/problems/find-smallest-common-element-in-all-rows/.

Problem Solution

#O(M*N(Log(M)))) Time, O(1) Space
class Solution:
    def smallestCommonElement(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
       
        for num in mat[0]:
            for row in range(1, m):
                left, right = 0, n - 1
                while left < right:
                    mid = (left + right) // 2
                    if mat[row][mid] < num:
                        left = mid + 1
                    else:
                        right = mid
                if mat[row][left] == num:
                    if row == m - 1:
                        return num
                    else:
                        continue
                else:
                    break
       
        return -1

Problem Explanation

If we are given an array or a matrix in sorted order, and we are asked to find a specific target, that is typically an indication that a binary search can be applied.

Each row is in sorted order, so we can iteratively pick a number from the first row and perform a binary search on each additional row until we find a common element in each row. 

Since the first row is in sorted order, the first common element we find will be the smallest.

Let's start by saving the length and width of the matrix so that we don't have to keep rewriting this later.

        m, n = len(mat), len(mat[0])

 

Now we will begin picking numbers from the first row.

        for num in mat[0]:

 

For each row after that, we will run a binary search to see if that number exists in the given row.

            for row in range(1, m):

 

We'll initialize a left and right pointer at the first and last indices of the row.

                left, right = 0, n - 1

 

While these pointers haven't overlapped, we will continue searching.

                while left < right:

 

Let's start each search iteration by taking a mean index between the left and right pointers.

                    mid = (left + right) // 2

 

If that element is less than the target number picked in the first row, we will eliminate the left side of the current search space by moving the left pointer one index past the mid.

                    if mat[row][mid] < num:
                        left = mid + 1

 

Otherwise, we will eliminate the right side.

                    else:
                        right = mid

 

Now we will see if we were able to find the target number within the current row.

If the value that the pointers overlapped on is the target number, and we are in the last row, then we will return the number.

                if mat[row][left] == num:
                    if row == m - 1:
                        return num

 

If we did find the number but aren't at the last row yet, we will continue to the next row.

                    else:
                        continue

 

If the value that the pointers overlapped on isn't the target number, then it didn't exist within the current row so we will break and choose the next number from the first row.

                else:
                    break

 

If we couldn't find a number in the first row that exists in all of the others, we will return a negative one.

        return -1