We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Smallest Common Element in All Rows

Number: 1143

Difficulty: Medium

Paid? Yes

Companies: Microsoft

Problem Description

Given an m x n matrix mat where every row is sorted in strictly increasing order, return the smallest common element that appears in all rows. If there is no common element, return -1.

Key Insights

  • Since every row is strictly increasing, binary search can be used efficiently to check for the presence of an element in a row.
  • Iterating over the first row’s elements and verifying their presence in all other rows is an effective approach.
  • Early termination is possible if an element is not found in any one row.
  • Time complexity is manageable given the constraints, even using binary search for each candidate across rows.

Space and Time Complexity

Time Complexity: O(m * n * log(n)) where m is the number of rows and n is the number of columns (binary search in each row for each candidate from the first row).
Space Complexity: O(1) (only a few auxiliary variables are used).

Solution

The solution iterates over each element (candidate) in the first row of the matrix. For each candidate, it checks if the candidate is present in every other row using binary search, taking advantage of the sorted order. If a candidate is found in every row, return it immediately as it will be the smallest such common element because the first row is processed in order. If no candidate is common across all rows, return -1.

Code Solutions

def smallestCommonElement(mat):
    # Get number of rows and columns
    m = len(mat)
    n = len(mat[0])
    
    # Helper function: binary search for target in a row
    def binary_search(row, target):
        left, right = 0, n - 1
        while left <= right:
            mid = (left + right) // 2
            if row[mid] == target:
                return True
            elif row[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return False
    
    # Iterate over each candidate in the first row
    for candidate in mat[0]:
        is_common = True
        # Check each subsequent row for the candidate using binary search
        for i in range(1, m):
            if not binary_search(mat[i], candidate):
                is_common = False
                break
        if is_common:
            return candidate
    return -1

# Example usage:
print(smallestCommonElement([[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]))
← Back to All Questions