2540. Minimum Common Value

Array
Two Pointers

TIME

O(n + m)

SPACE

O(1)

Intuition

Both arrays are already sorted, so the first equal pair we find while scanning from left to right is the minimum common value.

If the current value in nums1 is smaller, it can never match the current or any earlier value in nums2, so move the nums1 pointer forward. Do the symmetric move when the current value in nums2 is smaller.

Approach

Start two pointers at the beginning of both arrays.
Compare nums1[i] and nums2[j].
If they are equal, return that value.
Move the pointer with the smaller value.
If either pointer reaches the end, no common value exists, so return -1.

Complexity

Time: O(n + m), each pointer only moves forward
Space: O(1)

Edge Cases

The first elements are equal -> return immediately
No common values -> return -1
Arrays contain duplicates -> duplicates are naturally skipped by pointer movement
One array's values are all smaller than the other's

Code

from typing import List


class Solution:
    def getCommon(self, nums1: List[int], nums2: List[int]) -> int:
        """
        2540. Minimum Common Value
        Time: O(n + m)
        Space: O(1)
        """
        i = 0
        j = 0

        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                return nums1[i]

            if nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1

        return -1

/**
 * 2540. Minimum Common Value
 * Time: O(n + m)
 * Space: O(1)
 */
class Solution {
    public int getCommon(int[] nums1, int[] nums2) {
        int i = 0;
        int j = 0;

        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                return nums1[i];
            }

            if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }

        return -1;
    }
}