Minimum Common Value
Description
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.
Example 2:
Input: nums1 = [1, 2, 3, 6], nums2 = [2, 3, 4, 5]
Output: 2
Explanation: 2 and 3 are common. The minimum is 2.
Example 3:
Input: nums1 = [1, 2], nums2 = [3, 4]
Output: -1
Explanation: No common elements exist.
Constraints
1 <= nums1.length, nums2.length <= 10^51 <= nums1[i], nums2[j] <= 10^9Both nums1 and nums2 are sorted in non-decreasing order
Complexity
Show Complexity
- Time:
O(n + m) - Space:
O(1)
Hints
Show Hints
- Pattern
- Two pointers on sorted arrays
- Approach
- Use pointer i for nums1 and j for nums2. If nums1[i] < nums2[j], increment i. If nums1[i] > nums2[j], increment j. If equal, return that value (it's the minimum common since we traverse in order).
- Complexity
- Since both arrays are sorted, use two pointers to traverse simultaneously
Solutions
Show PY Solution
def solution(nums1, nums2):
i = 0
j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] > nums2[j]:
j += 1
elif nums1[i] < nums2[j]:
i += 1
else:
return nums1[i]
return -1