Find Smallest Common Element In All Rows - Leetcode Solution

Problem statement:

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.

Solution:

The main idea to solve this problem is to take advantage of the fact that each row is sorted in increasing order. We can use a hash table to keep track of the number of occurrences of each element in the matrix. Initially, we insert all the elements in the first row into the hash table. Then, for each subsequent row, we check if each element exists in the hash table. If it does, we increment its count in the hash table. If it doesn't, we skip it. Finally, we iterate through the hash table to find the element with count equal to the number of rows in the matrix.

Algorithm:

1. Initialize a hash table to keep track of the number of occurrences of each element in the matrix.
2. Insert all the elements in the first row of the matrix into the hash table.
3. For each subsequent row i from 1 to n-1: a. For each element j in row i: i. If j exists in the hash table, increment its count in the hash table. ii. If j doesn't exist in the hash table, skip it.
4. Iterate through the hash table to find the element with count equal to the number of rows in the matrix.
5. If such an element is found, return it.
6. If not, return -1.

Time Complexity:

The time complexity of the above algorithm is O(nm), where n is the number of rows and m is the number of columns in the matrix. This is because we iterate through each element in the matrix and insert it into the hash table or check its count in the hash table.

Space Complexity:

The space complexity of the above algorithm is O(m), where m is the number of columns in the matrix. This is because we only need to store the number of occurrences of each element in the hash table.

Implementation:

Here is the Python code for the above algorithm:

def smallestCommonElement(mat):
    counts = {}
    for j in mat[0]:
        counts[j] = 1

    for i in range(1, len(mat)):
        for j in mat[i]:
            if j in counts:
                counts[j] += 1

    for j in counts:
        if counts[j] == len(mat):
            return j

    return -1

Example:

Input:

mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]]

Output:

5

Explanation: All rows contain the element 5, which is the smallest common element.

1