Minimum Common Value - Solution & Explanation
Problem Statement
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 <= 1051 <= nums1[i], nums2[j] <= 109- Both
nums1andnums2are sorted in non-decreasing order.
Approach Overview
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.
Approach 1: Two-Pointer Technique
This approach utilizes the fact that both arrays are sorted. Using two pointers, one for each array, we traverse the arrays to find the smallest common value:
- Initialize two pointers at the start of each array.
- Compare the elements pointed by the pointers.
- If both elements are equal, you've found the minimum common integer.
- If the element at the first pointer is less than the element at the second pointer, increment the first pointer; otherwise, increment the second pointer.
- Continue this process until a match is found or one of the pointers reaches the end of its respective array.
- If no common element is found, return -1.
This code uses a two-pointer technique to find the minimum common value. It initializes two pointers at the beginning of both arrays and progresses them based on the comparison of the elements they point to. If an equal element is found on both sides, it is the smallest common element due to sorted nature of arrays, and thus it is returned. If no common element is found until any one pointer reaches the end, -1 is returned.
Complexity
Time Complexity: O(n + m), where n and m are the lengths of the two arrays. We only traverse each array once.
Space Complexity: O(1), no additional space is used apart from a few variables.
Approach 2: HashSet Intersection
This approach uses a HashSet to store the elements of the smaller array, providing a quick way to check for common elements:
- Insert all elements of the smaller array into a HashSet to minimize space usage.
- Iterate through the larger array and for each element, check if it exists in the HashSet.
- If a common element is found, return it as the minimum common value due to sorted order.
- If not, return -1 after iterating through the array.
- This ensures we keep the lookup time for elements O(1) by using HashSet.
This C solution uses a combination of manual sorting and binary searching with the help of C's standard library functions to find a common minimum element. The input is checked, potentially swapped for size optimization, then sorted and binary searched for elements presence.
Complexity
Time Complexity: O(n log n + m), mainly due to qsort and possibly bsearch in the worst case scenario per element in the second array.
Space Complexity: O(n), additional space used for sorting elements.
Approach 3: Two Pointers
Traverse the two arrays. If the elements pointed to by the two pointers are equal, return that element. If the elements pointed to by the two pointers are not equal, move the pointer pointing to the smaller element to the right by one bit until an equal element is found or the array is traversed.
The time complexity is O(m + n), where m and n are the lengths of the two arrays respectively. The space complexity is O(1).
Approach 4: Default Approach
Code
Rust
Complexity Comparison
| Approach | Complexity |
|---|---|
| Two-Pointer Technique | Time Complexity: O(n + m), where n and m are the lengths of the two arrays. We only traverse each array once. |
| HashSet Intersection | Time Complexity: O(n log n + m), mainly due to qsort and possibly bsearch in the worst case scenario per element in the second array. |
| Two Pointers | — |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Technique | O(n + m) | O(1) | Best choice when both arrays are sorted and you want the optimal linear scan |
| HashSet Intersection | O(n + m) | O(n) | Useful when arrays are not guaranteed to be sorted or quick lookups are preferred |
| Binary Search | O(n log m) | O(1) | Works well when one array is much smaller than the other |
Video Solution
2540. Minimum Common Value | 3 Approaches | HashMap | 2 Pointers | Binary Search • Aryan Mittal • 2,105 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Common Value easy or hard?
Minimum Common Value Python/Java solution
How to solve Minimum Common Value in O(n)?
What is the best approach for Minimum Common Value?
Is Minimum Common Value asked at Google/Amazon/Meta?
What data structure is used in Minimum Common Value?
What is the time complexity of Minimum Common Value?
Ready to solve this problem?
Practice Minimum Common Value with our built-in code editor and test cases.
Practice on FleetCode