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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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 | 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. |
2540. Minimum Common Value | 3 Approaches | HashMap | 2 Pointers | Binary Search • Aryan Mittal • 1,473 views views
Watch 9 more video solutions →Practice Minimum Common Value with our built-in code editor and test cases.
Practice on FleetCode