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] <= 109nums1 and nums2 are sorted in non-decreasing order.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.
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:
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.
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.
This approach uses a HashSet to store the elements of the smaller array, providing a quick way to check for common elements:
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.
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.
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).
Rust
| 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 | — |
| 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 |
Minimum Common Value | 3 Approaches | Leetcode 2540 • codestorywithMIK • 3,821 views views
Watch 9 more video solutions →Practice Minimum Common Value with our built-in code editor and test cases.
Practice on FleetCode