Jobs

Interviews

Discussions

Find Smallest Common Element in All Rows

Medium

Asked by:

12 views

Topics:

Arrays

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:

1 <= m, n <= 500
1 <= mat[i][j] <= 10⁴
mat[i] is sorted in strictly increasing order.

Try coding it in LeetCode

Find Smallest Common Element in All Rows

Medium

Asked by:

12 views

Topics:

Arrays

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:

1 <= m, n <= 500
1 <= mat[i][j] <= 10⁴
mat[i] is sorted in strictly increasing order.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the matrix, and what is the maximum value of an element in the matrix?
Can the matrix be empty, or can any of the rows be empty?
Is it guaranteed that each row is sorted in strictly non-decreasing order, or are duplicate values allowed within a row?
If multiple common elements exist, are we required to return the absolute smallest, or is returning any common element acceptable?
What is the expected return value if the input matrix is null?

Brute Force Solution

Approach

We're looking for a number that appears in every single row of a table. The brute force way is to check every possible number to see if it meets this condition. It's like manually checking each student's name on every class roster to see if they're enrolled in all classes.

Here's how the algorithm would work step-by-step:

Take the very first number from the very first row.
Go through every other row and see if that same number exists in each of them.
If the number is present in ALL of the other rows, then you've found your answer.
If the number is NOT present in ALL of the other rows, then that number is not the answer, so discard it.
Now take the next number from the first row and repeat the process, checking if it exists in every other row.
Keep doing this until you have checked every number from the first row.
If, after checking all the numbers from the first row, you haven't found a number present in every row, then there is no common number.

Code Implementation

def find_smallest_common_element(matrix):
    first_row = matrix[0]
    common_elements = []

    for number_to_check in first_row:
        is_common = True

        # Check if the number is present in all other rows
        for row in matrix[1:]:
            if number_to_check not in row:
                is_common = False
                break

        # If the number is common, add it to the list
        if is_common:
            common_elements.append(number_to_check)

    # Find the smallest element among common elements
    if common_elements:
        return min(common_elements)

    # If no common element is found, return -1
    return -1

Big(O) Analysis

Time Complexity

O(m*n) – Let 'm' be the number of rows in the input matrix and 'n' be the number of columns (or the number of elements in each row). The algorithm iterates through each element of the first row, which takes 'n' steps. For each element in the first row, the algorithm checks if that element exists in every other row, which takes 'm-1' row lookups and each row lookup can take upto 'n' steps to find the element in the respective row. Therefore, in the worst case we are performing n*(m-1)*n operations which simplifies to O(m*n^2). Considering rows can vary widely in number of elements, it is more accurate to say row lookups can be upto 'n', hence the complexity is better expressed as O(m*n).

Space Complexity

O(1) – The provided algorithm iterates through the first row and then, for each element in the first row, it searches for that element in every other row. The plain English explanation doesn't suggest using any auxiliary data structures like hash maps, sets, or lists to store intermediate results or track seen elements. The algorithm only needs a few variables to keep track of the current element being checked and to potentially flag whether that element is present in all rows. Therefore, the space complexity is constant, independent of the input array's dimensions.

Optimal Solution

Approach

The most efficient way to find a common element across multiple lists is to leverage the fact that the lists are sorted. We can use a process of elimination by comparing the smallest element in each list and advancing the one that's smallest until we find a common element or exhaust a list.

Here's how the algorithm would work step-by-step:

Start by looking at the first number in each list.
Find the smallest number among all the 'first' numbers.
If all the 'first' numbers are the same, you've found a number that's in all lists. This is your answer. If not, proceed to the next step.
If they aren't all the same, find the list where the smallest number came from.
Move to the next number in that particular list.
Repeat steps 2-5 until you find a number that's the same in all lists, or until you run out of numbers in one of the lists. If you run out of numbers in a list, it means there's no common number.

Code Implementation

def find_smallest_common_element(matrix):
    row_count = len(matrix)
    column_count = len(matrix[0])
    element_counts = {}

    for row in matrix:
        for element in row:
            if element in element_counts:
                element_counts[element] += 1
            else:
                element_counts[element] = 1

    common_elements = []

    # Find numbers that appear in every row
    for element, count in element_counts.items():
        if count == row_count:
            common_elements.append(element)

    #Check if there are any common elements
    if not common_elements:
        return -1

    #If there are common elements, find the smallest
    smallest_element = common_elements[0]

    for element in common_elements:
        if element < smallest_element:
            smallest_element = element

    return smallest_element

Big(O) Analysis

Time Complexity

O(m*n) – Let n be the length of the shortest list, and m be the number of lists. In the worst-case scenario, we might have to iterate through each element of the shortest list. For each element in the shortest list, we potentially compare it against the current 'first' element of the other m-1 lists. Therefore, the dominant operation is comparing elements across the lists and incrementing the pointer of the list with the smallest value until a common element is found or a list is exhausted. The total number of comparisons and increments can be approximated as m*n, leading to a time complexity of O(m*n).

Space Complexity

O(1) – The algorithm uses a fixed number of index variables, one for each list, to track the current element being considered in each row. Regardless of the number of rows or the size of each row, the number of index variables remains constant. No additional data structures like hash maps or auxiliary arrays are used to store intermediate results. Therefore, the auxiliary space complexity is O(1), indicating constant space.

Edge Cases

Case	How to Handle
Empty matrix (mat is null or has zero rows)	Return -1 immediately since there are no rows to find a common element in.
Matrix with an empty row (one of mat[i] is null or empty)	Return -1 immediately if any row is empty, as no common element can exist across all rows.
Matrix with a single row	Return the first element of the single row if it exists or -1 if the row is empty.
Matrix with all rows containing the same element at the beginning	The algorithm should correctly identify that element as the smallest common element.
Matrix with duplicate elements within the same row	The algorithm should handle duplicates within rows without incorrectly reporting the smallest common element.
No common element exists across all rows	The algorithm should correctly identify that there is no common element and return -1.
Integer overflow with extremely large numbers in the matrix	Consider using a data type with a larger range (e.g., long) if integer overflow is a concern, or check for overflow during comparisons.
Matrix with very large dimensions (large number of rows and columns)	Ensure the algorithm's time complexity remains reasonable to prevent timeouts; prefer an algorithm with a near-linear time complexity if possible, such as using pointers to track the smallest element in each row.

Empty matrix (mat is null or has zero rows)

How to Handle:

Return -1 immediately since there are no rows to find a common element in.

Matrix with an empty row (one of mat[i] is null or empty)

How to Handle:

Return -1 immediately if any row is empty, as no common element can exist across all rows.

Matrix with a single row

How to Handle:

Return the first element of the single row if it exists or -1 if the row is empty.

Matrix with all rows containing the same element at the beginning

How to Handle:

The algorithm should correctly identify that element as the smallest common element.

Matrix with duplicate elements within the same row

How to Handle:

The algorithm should handle duplicates within rows without incorrectly reporting the smallest common element.

No common element exists across all rows

How to Handle:

The algorithm should correctly identify that there is no common element and return -1.

Integer overflow with extremely large numbers in the matrix

How to Handle:

Consider using a data type with a larger range (e.g., long) if integer overflow is a concern, or check for overflow during comparisons.

Matrix with very large dimensions (large number of rows and columns)

How to Handle:

Ensure the algorithm's time complexity remains reasonable to prevent timeouts; prefer an algorithm with a near-linear time complexity if possible, such as using pointers to track the smallest element in each row.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the matrix, and what is the maximum value of an element in the matrix?
Can the matrix be empty, or can any of the rows be empty?
Is it guaranteed that each row is sorted in strictly non-decreasing order, or are duplicate values allowed within a row?
If multiple common elements exist, are we required to return the absolute smallest, or is returning any common element acceptable?
What is the expected return value if the input matrix is null?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the very first number from the very first row.
Go through every other row and see if that same number exists in each of them.
If the number is present in ALL of the other rows, then you've found your answer.
If the number is NOT present in ALL of the other rows, then that number is not the answer, so discard it.
Now take the next number from the first row and repeat the process, checking if it exists in every other row.
Keep doing this until you have checked every number from the first row.
If, after checking all the numbers from the first row, you haven't found a number present in every row, then there is no common number.

Code Implementation

def find_smallest_common_element(matrix):
    first_row = matrix[0]
    common_elements = []

    for number_to_check in first_row:
        is_common = True

        # Check if the number is present in all other rows
        for row in matrix[1:]:
            if number_to_check not in row:
                is_common = False
                break

        # If the number is common, add it to the list
        if is_common:
            common_elements.append(number_to_check)

    # Find the smallest element among common elements
    if common_elements:
        return min(common_elements)

    # If no common element is found, return -1
    return -1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by looking at the first number in each list.
Find the smallest number among all the 'first' numbers.
If all the 'first' numbers are the same, you've found a number that's in all lists. This is your answer. If not, proceed to the next step.
If they aren't all the same, find the list where the smallest number came from.
Move to the next number in that particular list.
Repeat steps 2-5 until you find a number that's the same in all lists, or until you run out of numbers in one of the lists. If you run out of numbers in a list, it means there's no common number.

Code Implementation

def find_smallest_common_element(matrix):
    row_count = len(matrix)
    column_count = len(matrix[0])
    element_counts = {}

    for row in matrix:
        for element in row:
            if element in element_counts:
                element_counts[element] += 1
            else:
                element_counts[element] = 1

    common_elements = []

    # Find numbers that appear in every row
    for element, count in element_counts.items():
        if count == row_count:
            common_elements.append(element)

    #Check if there are any common elements
    if not common_elements:
        return -1

    #If there are common elements, find the smallest
    smallest_element = common_elements[0]

    for element in common_elements:
        if element < smallest_element:
            smallest_element = element

    return smallest_element

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty matrix (mat is null or has zero rows)	Return -1 immediately since there are no rows to find a common element in.
Matrix with an empty row (one of mat[i] is null or empty)	Return -1 immediately if any row is empty, as no common element can exist across all rows.
Matrix with a single row	Return the first element of the single row if it exists or -1 if the row is empty.
Matrix with all rows containing the same element at the beginning	The algorithm should correctly identify that element as the smallest common element.
Matrix with duplicate elements within the same row	The algorithm should handle duplicates within rows without incorrectly reporting the smallest common element.
No common element exists across all rows	The algorithm should correctly identify that there is no common element and return -1.
Integer overflow with extremely large numbers in the matrix	Consider using a data type with a larger range (e.g., long) if integer overflow is a concern, or check for overflow during comparisons.
Matrix with very large dimensions (large number of rows and columns)	Ensure the algorithm's time complexity remains reasonable to prevent timeouts; prefer an algorithm with a near-linear time complexity if possible, such as using pointers to track the smallest element in each row.

Empty matrix (mat is null or has zero rows)

How to Handle:

Return -1 immediately since there are no rows to find a common element in.

Matrix with an empty row (one of mat[i] is null or empty)

How to Handle:

Return -1 immediately if any row is empty, as no common element can exist across all rows.

Matrix with a single row

How to Handle:

Return the first element of the single row if it exists or -1 if the row is empty.

Matrix with all rows containing the same element at the beginning

How to Handle:

The algorithm should correctly identify that element as the smallest common element.

Matrix with duplicate elements within the same row

How to Handle:

The algorithm should handle duplicates within rows without incorrectly reporting the smallest common element.

No common element exists across all rows

How to Handle:

The algorithm should correctly identify that there is no common element and return -1.

Integer overflow with extremely large numbers in the matrix

How to Handle:

Consider using a data type with a larger range (e.g., long) if integer overflow is a concern, or check for overflow during comparisons.

Matrix with very large dimensions (large number of rows and columns)

How to Handle: