Minimum Common Value

Difficulty: Easy | Acceptance: 58.00% | Paid: No Topics: Array, Hash Table, Two Pointers, Binary Search

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. An integer common to both arrays is considered common if it appears at least once in each array.

• Examples
• Constraints
• Brute Force
• Hash Set
• Two Pointers
• Binary Search

Examples

Example 1:

Input: nums1 = [1,2,3], nums2 = [2,4]
Output: 2
Explanation: The smallest integer common to both arrays is 2.

Example 2:

Input: nums1 = [1,2,3,6], nums2 = [7,1]
Output: 1
Explanation: The smallest integer common to both arrays is 1.

Constraints

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

Brute Force

Intuition Iterate through every element in the first array and, for each element, check if it exists in the second array. Since the arrays are sorted, we can optimize the inner loop slightly by breaking early if the current element in nums2 exceeds the target.

Steps

• Iterate through each element x in nums1.
• For each x, iterate through nums2 to find a match.
• If a match is found, return x immediately (since nums1 is sorted, this is the minimum).
• If the loop finishes without finding a match, return -1.

class Solution:
    def getCommon(self, nums1: list[int], nums2: list[int]) -> int:
        for x in nums1:
            for y in nums2:
                if x == y:
                    return x
                if y > x:
                    break
        return -1

Complexity

• Time: O(n * m) in the worst case, where n and m are the lengths of the arrays.
• Space: O(1)
• Notes: This approach is inefficient for large inputs but serves as a baseline.

Hash Set

Intuition Store all elements of the first array in a hash set for O(1) lookups. Then iterate through the second array and return the first element found in the set.

Steps

• Create a set from nums1.
• Iterate through nums2.
• If an element from nums2 exists in the set, return it.
• If the loop ends, return -1.

class Solution:
    def getCommon(self, nums1: list[int], nums2: list[int]) -> int:
        s = set(nums1)
        for x in nums2:
            if x in s:
                return x
        return -1

Complexity

• Time: O(n + m)
• Space: O(n) to store the set.
• Notes: Fast time complexity but trades off memory usage proportional to the size of the first array.

Two Pointers

Intuition Since both arrays are sorted, we can traverse them simultaneously using two pointers. Compare the elements at the current pointers; move the pointer pointing to the smaller value forward to try and find a match.

Steps

• Initialize two pointers, i and j, to 0.
• While both pointers are within their array bounds:
  • If nums1[i] == nums2[j], return the value.
  • If nums1[i] < nums2[j], increment i.
  • Otherwise, increment j.
• Return -1 if no match is found.

class Solution:
    def getCommon(self, nums1: list[int], nums2: list[int]) -> int:
        i = j = 0
        n, m = len(nums1), len(nums2)
        while i < n and j < m:
            if nums1[i] == nums2[j]:
                return nums1[i]
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1
        return -1

Complexity

• Time: O(n + m)
• Space: O(1)
• Notes: This is the optimal approach for sorted arrays, utilizing constant extra space.

Binary Search

Intuition Iterate through the smaller array (or just nums1) and perform a binary search for each element in the second array. Since nums2 is sorted, binary search is efficient.

Steps

• Iterate through each element x in nums1.
• Perform binary search for x in nums2.
• If found, return x (since nums1 is sorted, the first found is the minimum).
• If the loop finishes, return -1.

import bisect

class Solution:
    def getCommon(self, nums1: list[int], nums2: list[int]) -> int:
        for x in nums1:
            idx = bisect.bisect_left(nums2, x)
            if idx < len(nums2) and nums2[idx] == x:
                return x
        return -1

Complexity

• Time: O(n log m) or O(min(n, m) log max(n, m))
• Space: O(1)
• Notes: Useful if one array is significantly smaller than the other, though generally slower than the Two Pointers approach for similar sizes.