Minimum Common Value

Problem Statement

The task is to determine the smallest integer common between two sorted arrays, nums1 and nums2. Each array is sorted in non-decreasing order, and we need to find the minimum integer that appears in both. If there's no common integer, the function should return -1. This common integer is defined as an element that occurs at least once in both arrays. The goal is to write a function that efficiently finds this minimum common integer by leveraging the fact that both lists are sorted.

Examples

Example 1

Input:

nums1 = [1,2,3], nums2 = [2,4]

Output:

2

Explanation:

The smallest element common to both arrays is 2, so we return 2.

Example 2

Input:

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

Output:

2

Explanation:

There are two common elements in the array 2 and 3 out of which 2 is the smallest, so 2 is returned.

Constraints

• 1 <= nums1.length, nums2.length <= 105
• 1 <= nums1[i], nums2[j] <= 109
• Both nums1 and nums2 are sorted in non-decreasing order.

Approach and Intuition

The problem revolves around finding a common element between two sorted arrays. Given the sorted nature of the arrays, a two-pointer technique offers a clear path towards an efficient solution.

Step by Step Approach:

1. Initialize two pointers, i for nums1 and j for nums2, starting from the zeroth index.
2. Use a loop to continue the process as long as both pointers are within the boundaries of their respective arrays.
3. Compare the elements pointed by i and j:
   • If nums1[i] is equal to nums2[j], this is the smallest common element (since arrays are sorted), and you can return nums1[i].
   • If nums1[i] is less than nums2[j], increment i to catch up with j as we might find a common element when nums1[i] increases.
   • Conversely, if nums2[j] is less than nums1[i], increment j to make nums2[j] catch up with nums1[i].
4. If the loop terminates, it means there is no common element, thus return -1.

Intuition:

• The two-pointer technique leverages the sorted order of arrays to skip checking each combination of elements, potentially reducing the comparison from a quadratic complexity approach to linear.
• Since the target is finding the minimum common integer, comparing elements sequentially from the start naturally checks the smaller integers first.

Scenarios from the given Examples

• Example 1: Here, as soon as both pointers point to 2, which is found common in both arrays, it's immediately returned.
• Example 2: The approach is similar; the smallest common element (2) is identified before checking other elements like 3.

Solutions

class Solution {
public:
    int findShared(vector<int>& arr1, vector<int>& arr2) {
        if (arr1.size() > arr2.size()) {
            return findShared(arr2, arr1);
        }
    
        for (int element : arr1) {
            if (performBinarySearch(element, arr2)) {
                return element;
            }
        }
    
        return -1;
    }
    
private:
    bool performBinarySearch(int key, vector<int>& data) {
        int low = 0;
        int high = data.size() - 1;
    
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (data[mid] > key) {
                high = mid - 1;
            } else if (data[mid] < key) {
                low = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }
};