Minimum Common Value - Leetcode Solution

Problem Statement:

Given n arrays of integers, find the minimum common value (MCV) which is the smallest number that is present in each of the n arrays. If there is no MCV, return -1.

Example:

Input: [[3,4,5,6],[2,3,4,7],[1,2,3,4]] Output: 3 Explanation:

• 3 is a common value in all the given arrays
• 4 is a common value in the first two arrays, but not in the third array
• 2 is a common value in the second and third arrays, but not in the first array
• 1, 5, 6, and 7 are not common values in any of the given arrays

Solution:

One way to approach this problem is to use a hash table to keep track of the frequency of each number in all the arrays. We can start by iterating through the first array and adding the frequency count of each number to the hash table. Then, for each subsequent array, we can update the frequency count of each number in the hash table by checking if it exists in the hash table and incrementing its count if it does.

Once we have updated the frequency counts for all the arrays, we can iterate through the hash table and check if the frequency count of each number is equal to the number of arrays. If it is, then that means the number is present in all the arrays and is a candidate for the MCV.

We can then iterate through the hash table again and find the smallest number that has a frequency count equal to the number of arrays. This will be the MCV. If there is no number with a frequency count equal to the number of arrays, then we return -1 to indicate that there is no MCV.

Here is the Python code for the solution:

def find_MCV(arrs):
    freq = {}
    n = len(arrs)
    
    # populate hash table with frequency count of first array
    for num in arrs[0]:
        freq[num] = 1
        
    # update frequency count for each subsequent array
    for i in range(1, n):
        for num in arrs[i]:
            if num in freq:
                freq[num] += 1
                
    # find smallest number with frequency count equal to n
    mcv = float('inf')
    for num, count in freq.items():
        if count == n:
            mcv = min(mcv, num)
            
    return mcv if mcv != float('inf') else -1

The time complexity of this solution is O(n*m) where n is the number of arrays and m is the maximum length of an array. The space complexity is also O(m) to store the hash table.

1