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^5
1 <= nums1[i], nums2[j] <= 10^9
Both nums1 and nums2 are sorted in non-decreasing order

Signature

def solution(nums1: list[int], nums2: list[int]) -> int: ...

Complexity

Time: O(n + m)
Space: O(1)

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

Python

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