We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Common Value

Number: 2634

Difficulty: Easy

Paid? No

Companies: Amazon, Microsoft

Problem Description

Given two sorted integer arrays, nums1 and nums2, find and return the minimum common integer between them. If there is no common integer, return -1.

Key Insights

  • Both arrays are sorted in non-decreasing order.
  • A two-pointer approach can efficiently traverse the arrays simultaneously.
  • Alternatively, binary search or hash table based methods can also be applied.
  • The goal is to find the smallest integer that appears in both arrays.

Space and Time Complexity

Time Complexity: O(n + m) where n and m are the lengths of nums1 and nums2. Space Complexity: O(1) (ignoring the input storage).

Solution

We use the two-pointer technique to traverse both sorted arrays. Starting with pointers at the beginning of each array, we compare the pointed elements:

  • If they are equal, we have found the smallest common value.
  • If the element in nums1 is smaller, we move the pointer in nums1 ahead.
  • Otherwise, we move the pointer in nums2 ahead. This approach works because the arrays are sorted, ensuring that once we find a common value it will be the smallest one possible.

Code Solutions

# Define the function to find the minimum common value
def get_common(nums1, nums2):
    # Initialize two pointers for arrays nums1 and nums2
    pointer1, pointer2 = 0, 0

    # Loop until one pointer runs out of elements
    while pointer1 < len(nums1) and pointer2 < len(nums2):
        # When the current elements are equal, we've found a common value
        if nums1[pointer1] == nums2[pointer2]:
            return nums1[pointer1]
        # Move the pointer that points to the smaller element
        elif nums1[pointer1] < nums2[pointer2]:
            pointer1 += 1
        else:
            pointer2 += 1

    # No common element found, return -1
    return -1

# Example usage:
if __name__ == "__main__":
    # Example test case
    nums1 = [1, 2, 3, 6]
    nums2 = [2, 3, 4, 5]
    print(get_common(nums1, nums2))  # Expected output: 2
← Back to All Questions