Minimum Common Value

Minimum Common Value

What is this problem about?

The Minimum Common Value problem gives you two sorted integer arrays, nums1 and nums2. You need to find the smallest integer that appears in both arrays. If there is no common element, return -1.

Why is this asked in interviews?

This is a high-yield Minimum Common Value interview question at Microsoft and Google. It tests your knowledge of Two Pointers and Binary Search. It evaluates your ability to leverage the fact that the input arrays are already sorted, which is the key to an optimal $O(N+M)$ or $O(N \log M)$ solution.

Algorithmic pattern used

The Two Pointers interview pattern is usually preferred for its simplicity and linear time complexity.

1. Place pointer i at the start of nums1 and j at the start of nums2.
2. If nums1[i] == nums2[j], you've found the minimum common value.
3. If nums1[i] < nums2[j], increment i to find a larger value.
4. If nums1[i] > nums2[j], increment j.
5. Repeat until a match is found or one array is exhausted.

Example explanation

nums1 = [1, 2, 3], nums2 = [2, 4].

1. i=0 (1), j=0 (2). 1 < 2, so i++.
2. i=1 (2), j=0 (2). Match! Minimum common value = 2.

Common mistakes candidates make

• Using a Hash Set: Copying one array into a Set and checking elements of the other. While $O(N+M)$, it uses $O(N)$ extra space. With the two-pointer approach, you use $O(1)$ extra space.
• Nested loops: Checking every pair $(i, j)$ resulting in $O(N \cdot M)$ time.
• Not stopping early: Continuing to search after the first match is found. Since the arrays are sorted, the first match you encounter is guaranteed to be the minimum.

Interview preparation tip

Always check if your inputs are sorted. If they are, Two Pointers should be your first thought. If one array is significantly smaller than the other, consider Binary Search instead, which might be even faster.