Teaching Kids Programming – Algorithms to Find Minimum Common Value of Two Sorted Arrays (Binary Search, Two Pointer, Brute Force, Hash Set Intersection)


Teaching Kids Programming: Videos on Data Structures and Algorithms

Given two integer arrays nums1 and nums2, sorted in non-decreasing order, return the minimum integer common to both arrays. If there is no common integer amongst nums1 and nums2, return -1. Note that an integer is said to be common to nums1 and nums2 if both arrays have at least one occurrence of that integer.

Example 1:
Input: nums1 = [1,2,3], nums2 = [2,4]
Output: 2
Explanation: The smallest element common to both arrays is 2, so we return 2.

Example 2:
Input: nums1 = [1,2,3,6], nums2 = [2,3,4,5]
Output: 2
Explanation: There are two common elements in the array 2 and 3 out of which 2 is the smallest, so 2 is returned.

Constraints:
1 <= nums1.length, nums2.length <= 10^5
1 <= nums1[i], nums2[j] <= 10^9
Both nums1 and nums2 are sorted in non-decreasing order.

Hints:
Try to use a set.
Otherwise, try to use a two-pointer approach.

Minimum Common Value of Two Sorted Arrays (Brute Force Algorithm)

Given two arrays are already sorted, we can go through one array (from the smallest to the largest elements) and perform a linear search on the second array. Return the first element found in both arrays. The time complexity is O(NM) where N and M are the numbers of elements in these two arrays. The space complexity is O(1) constant.

1
2
3
4
5
6
7
class Solution:
    def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
        for i in nums1:
            for j in nums2:
                if i == j:
                    return i
        return -1
class Solution:
    def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
        for i in nums1:
            for j in nums2:
                if i == j:
                    return i
        return -1

And this can be shortened by the next function in one-liner:

1
return next((i for i in nums1 for j in nums2 if i == j), -1)
return next((i for i in nums1 for j in nums2 if i == j), -1)

Minimum Common Value of Two Sorted Arrays (Using a Hash Set)

We can convert the arrays to sets, and then use the intersection operator to find the common elements that appear in both arrays. And then we sort the common numbers if there is at least one, and then return the smallest one.

1
2
3
4
class Solution:
    def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
        x = sorted(set(nums1) & set(nums2))
        return x[0] if x else -1
class Solution:
    def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
        x = sorted(set(nums1) & set(nums2))
        return x[0] if x else -1

The time complexity is O(NLogN) because in the worst case, two arrays are identical and sorting N elements (each number is a common number) takes O(NLogN). The space complexity is O(N) sicne we need to hold the numbers in two sets.

This algorithm also works on unsorted arrays.

Minimum Common Value of Two Sorted Arrays (Two Pointer Algorithm)

Similar to merging two sorted lists, we can use two pointers to achieve the optimal performance here. We move the pointer that points to a smaller element. The time complexity is O(N+M) since it takes at most N+M steps. Two pointers both move only one direction which is to the right until either a common element is found or one is beyond the rightmost boundary.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
        n1, n2 = len(nums1), len(nums2)
        i = j = 0
        while i < n1 and j < n2:
            if nums1[i] == nums2[j]:
                return nums1[i]
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1
        return -1     
class Solution:
    def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
        n1, n2 = len(nums1), len(nums2)
        i = j = 0
        while i < n1 and j < n2:
            if nums1[i] == nums2[j]:
                return nums1[i]
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1
        return -1     

The space complexity is O(1) constant.

Minimum Common Value of Two Sorted Arrays (Binary Search via bisect_left)

We can go through one element and then binary search it in another array. This is similar to the first one except that we use the binary search instead of linear search. The time complexity is O(NLogM) or O(MLogN). It is better we binary search the longer array to bring down the time complexity.

1
2
3
4
5
6
7
8
9
10
class Solution:
    def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
        if len(nums1) > len(nums2):
            return self.getCommon(nums2, nums1)
        
        for i in nums1:
            x = bisect_left(nums2, i)
            if x < len(nums2) and nums2[x] == i:
                return i
        return -1
class Solution:
    def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
        if len(nums1) > len(nums2):
            return self.getCommon(nums2, nums1)
        
        for i in nums1:
            x = bisect_left(nums2, i)
            if x < len(nums2) and nums2[x] == i:
                return i
        return -1

The space complexity is O(1) constant. We can use bisect_left or bisect_right in Python to perform a binary search on a sorted array. If we use bisect_right, we have to subtract one:

1
if x <= len(nums2) and nums2[x-1] == i:
if x <= len(nums2) and nums2[x-1] == i:

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
946 words
Last Post: Teaching Kids Programming - Count Nodes Equal to Sum of Descendants (Recursive Depth First Search Algorithm)
Next Post: Teaching Kids Programming - Iterative Algorithm to Check if a Binary Tree is Symmetric

The Permanent URL is: Teaching Kids Programming – Algorithms to Find Minimum Common Value of Two Sorted Arrays (Binary Search, Two Pointer, Brute Force, Hash Set Intersection)

Leave a Reply