Problem Description

You are given two integer arrays nums1 and nums2 that are already sorted in non-decreasing order. Your task is to find the smallest integer that appears in both arrays.

The key requirements are:

• Both arrays are sorted in non-decreasing order (smallest to largest)
• Find the minimum integer that exists in both arrays
• An integer is considered "common" if it appears at least once in each array
• If no integer appears in both arrays, return -1

For example:

• If nums1 = [1, 2, 3] and nums2 = [2, 4], the common integer is 2, so return 2
• If nums1 = [1, 2, 3, 6] and nums2 = [2, 3, 4, 5], both 2 and 3 are common, but 2 is smaller, so return 2
• If nums1 = [1, 3, 5] and nums2 = [2, 4, 6], there are no common integers, so return -1

The solution uses a two-pointer technique to efficiently find the minimum common element. Starting from the beginning of both arrays (since they're sorted), it compares elements at positions i and j. When nums1[i] == nums2[j], that's the minimum common element (due to sorted order). When nums1[i] < nums2[j], pointer i advances since the current element in nums1 cannot exist in nums2 at or after position j. Similarly, when nums1[i] > nums2[j], pointer j advances. This continues until either a common element is found or one array is fully traversed.

Intuition

Since both arrays are sorted in non-decreasing order, we can leverage this property to find the common element efficiently. Think about it this way: if we're looking for the minimum common element, and both arrays are sorted, then the first common element we encounter while traversing from the beginning will automatically be the minimum.

The key insight is that we don't need to check every element in nums1 against every element in nums2 (which would take O(m*n) time). Instead, we can use two pointers moving through the arrays simultaneously.

Why does this work? Consider what happens when we compare two elements:

• If nums1[i] == nums2[j], we've found a common element, and since we're traversing from the smallest values, this must be the minimum common element.
• If nums1[i] < nums2[j], the current element in nums1 is too small to exist in nums2 at position j or beyond (since nums2 is sorted). So we need to move to a larger element in nums1 by incrementing i.
• If nums1[i] > nums2[j], similarly, the current element in nums2 is too small to match anything at position i or beyond in nums1, so we increment j.

This approach essentially "synchronizes" our traversal through both arrays, skipping elements that cannot possibly be common. We're always moving the pointer that points to the smaller element, gradually bringing both pointers toward potential matches. This guarantees we'll find the minimum common element if it exists, or exhaust at least one array if no common element exists.

The beauty of this solution is that it only requires one pass through the arrays with time complexity O(m + n) instead of the brute force O(m*n).

Learn more about Two Pointers and Binary Search patterns.

Solution Approach

The solution implements the two-pointer technique to efficiently find the minimum common element between two sorted arrays.

Implementation Details:

1. Initialize Two Pointers: Start with i = 0 for nums1 and j = 0 for nums2. Also store the lengths of both arrays as m = len(nums1) and n = len(nums2).

2. Traverse Both Arrays Simultaneously: Use a while loop that continues as long as both pointers are within their respective array bounds: while i < m and j < n.

3. Compare Elements at Current Positions:

   • Equal elements (nums1[i] == nums2[j]): This is our answer! Since both arrays are sorted and we're traversing from the beginning, this is guaranteed to be the minimum common element. Return nums1[i] immediately.

   • First element smaller (nums1[i] < nums2[j]): The element at nums1[i] cannot exist in nums2 from position j onward (due to sorted order). Move pointer i forward by incrementing i += 1.

   • Second element smaller (nums1[i] > nums2[j]): The element at nums2[j] cannot exist in nums1 from position i onward. Move pointer j forward by incrementing j += 1.

4. No Common Element Found: If the loop completes without finding any equal elements (meaning at least one pointer has reached the end of its array), return -1.

Why This Works:

• The sorted nature of both arrays ensures that when we find the first match, it's automatically the minimum.
• By always advancing the pointer pointing to the smaller element, we never miss a potential match.
• Each element in both arrays is visited at most once, giving us optimal time complexity of O(m + n).

Space Complexity: O(1) - only using two pointer variables and no additional data structures.

Example Walkthrough

Let's walk through the solution with a concrete example to see how the two-pointer technique works.

Example: nums1 = [1, 2, 4, 6, 8] and nums2 = [2, 3, 4, 7]

We'll trace through each step showing the pointer positions and comparisons:

Initial Setup:

• i = 0, j = 0
• nums1[i] = 1, nums2[j] = 2

Step 1: Compare nums1[0] = 1 with nums2[0] = 2

• Since 1 < 2, the element 1 cannot exist in nums2 from position 0 onward (since nums2 is sorted)
• Action: Increment i to 1
• State: i = 1, j = 0

Step 2: Compare nums1[1] = 2 with nums2[0] = 2

• Since 2 == 2, we found a common element!
• Since we're traversing from the beginning of both sorted arrays, this is guaranteed to be the minimum common element
• Return: 2

Let's verify this is correct by identifying all common elements:

• Common elements: 2 (at nums1[1] and nums2[0]), 4 (at nums1[2] and nums2[2])
• The minimum of these is 2 ✓

Alternative Scenario - No Common Element: Let's also see what happens when there's no common element.

Example: nums1 = [1, 3, 5] and nums2 = [2, 4, 6]

Step 1: nums1[0] = 1 vs nums2[0] = 2 → 1 < 2 → increment i to 1

Step 2: nums1[1] = 3 vs nums2[0] = 2 → 3 > 2 → increment j to 1

Step 3: nums1[1] = 3 vs nums2[1] = 4 → 3 < 4 → increment i to 2

Step 4: nums1[2] = 5 vs nums2[1] = 4 → 5 > 4 → increment j to 2

Step 5: nums1[2] = 5 vs nums2[2] = 6 → 5 < 6 → increment i to 3

Step 6: i = 3 equals length of nums1, so exit loop

Since we exhausted nums1 without finding any common element, return -1.

Solution Implementation

Time and Space Complexity

The time complexity is O(m + n), where m and n are the lengths of nums1 and nums2 respectively. In the worst case, when there is no common element or the common element is at the end of one of the arrays, the algorithm needs to traverse through all elements of both arrays. Each iteration of the while loop either increments i or j, and the loop continues until one of the pointers reaches the end of its respective array. Therefore, the maximum number of iterations is m + n.

The space complexity is O(1) as the algorithm only uses a constant amount of extra space. The variables i, j, m, and n are the only additional space used, regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting to Use Set Intersection Without Considering Minimum

A common mistake is converting both arrays to sets and using set intersection, then finding the minimum:

Incorrect Approach:

def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
    common = set(nums1) & set(nums2)
    return min(common) if common else -1

Why it's problematic:

• While this works correctly, it has O(m + n) space complexity instead of O(1)
• It doesn't leverage the fact that arrays are already sorted
• Finding min() requires additional O(k) time where k is the number of common elements

Better Solution: Stick with the two-pointer approach which finds the minimum directly in O(m + n) time with O(1) space.

2. Forgetting to Handle Duplicate Elements

Some might worry about duplicates and try to skip them unnecessarily:

Overcomplicated Approach:

def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
    i, j = 0, 0
    while i < len(nums1) and j < len(nums2):
        # Skip duplicates in nums1
        while i + 1 < len(nums1) and nums1[i] == nums1[i + 1]:
            i += 1
        # Skip duplicates in nums2
        while j + 1 < len(nums2) and nums2[j] == nums2[j + 1]:
            j += 1
          
        if nums1[i] == nums2[j]:
            return nums1[i]
        elif nums1[i] < nums2[j]:
            i += 1
        else:
            j += 1
    return -1

Why it's problematic:

• Adds unnecessary complexity
• The original solution handles duplicates naturally - when a match is found, it returns immediately
• Skipping duplicates doesn't improve the worst-case complexity

Better Solution: The original two-pointer approach handles duplicates correctly without special cases.

3. Using Binary Search Instead of Two Pointers

Some might think to iterate through one array and binary search in the other:

Suboptimal Approach:

def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
    for num in nums1:
        left, right = 0, len(nums2) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums2[mid] == num:
                return num
            elif nums2[mid] < num:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Why it's problematic:

• Time complexity becomes O(m * log n) instead of O(m + n)
• More complex to implement
• Less efficient for this specific problem

Better Solution: The two-pointer approach with O(m + n) time is more efficient than binary search's O(m * log n).

4. Not Returning Immediately Upon Finding First Match

Collecting all common elements before returning the minimum:

Inefficient Approach:

def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
    i, j = 0, 0
    common_elements = []
  
    while i < len(nums1) and j < len(nums2):
        if nums1[i] == nums2[j]:
            common_elements.append(nums1[i])
            i += 1
            j += 1
        elif nums1[i] < nums2[j]:
            i += 1
        else:
            j += 1
  
    return common_elements[0] if common_elements else -1

Why it's problematic:

• Uses extra space O(k) where k is the number of common elements
• Continues traversing even after finding the minimum
• Inefficient when the minimum appears early

Better Solution: Return immediately when the first (minimum) common element is found, as in the original solution.