Minimum Common Value - Video Solutions

Problem Overview: You are given two sorted integer arrays. The goal is to return the smallest value that appears in both arrays. If no such value exists, return -1. Since both arrays are already sorted in non‑decreasing order, you can exploit that property instead of checking every possible pair.

Approach 1: Two-Pointer Technique (O(n + m) time, O(1) space)

This approach leverages the sorted nature of both arrays. Start two pointers: i for nums1 and j for nums2. Compare the elements at both pointers. If the values are equal, that value is the smallest common element because both arrays are sorted and pointers move from the beginning. If nums1[i] < nums2[j], increment i to move toward a larger value. Otherwise increment j. Each step eliminates one element from consideration, so the arrays are scanned only once.

The key insight is that increasing the pointer on the smaller value moves closer to a potential match without missing any candidate. This makes the algorithm linear in the combined size of the arrays. It uses constant extra memory and is the most efficient solution when both arrays are sorted. This pattern appears frequently in two pointers and array problems where ordered data allows simultaneous traversal.

Approach 2: HashSet Intersection (O(n + m) time, O(n) space)

This method ignores the sorted property and instead relies on fast membership checks using a hash table. Insert all elements of the first array into a HashSet. Then iterate through the second array and check whether each value exists in the set. The first matching value encountered that also satisfies the "minimum" requirement can be tracked and returned.

Hash lookups run in average O(1) time, making the overall complexity linear relative to the total number of elements. The tradeoff is memory usage: storing the first array requires O(n) extra space. This technique demonstrates the classic tradeoff between time and space and is a common pattern in hash table problems where quick existence checks are required.

Binary Search Variation (O(n log m) time, O(1) space)

Because the arrays are sorted, you could also iterate through one array and perform a binary search for each value in the other. For every element in nums1, run binary search in nums2. If found, return the value immediately. This approach highlights how binary search works on sorted collections, though it is slower than the two‑pointer scan when both arrays must be processed.

Recommended for interviews: The two-pointer technique is the expected solution. It uses the sorted property directly and achieves optimal O(n + m) time with constant space. Mentioning the hash set approach shows you understand alternative strategies, but recognizing that sorted arrays allow a linear merge-style scan demonstrates stronger algorithmic thinking.