Problem Statement

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 nums if both arrays have at least one occurrence of that integer.

Example:

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

Different Approaches

Approach 1 (Hash Set)

Intuition:

There are two main kinds of hash tables: hash maps, which store (key, value) pairs, and hash sets, which store unique values. For this problem, we chose a hash set because we are concerned with whether an element exists, not the number of times it occurs. A hashmap could alternatively be used to solve this problem, where the element the element is the key and the frequency is the value.

We can add the elements in nums1 to a has set set1, where the element is the key.

Then, we can loop through nums2, and check whether each element is in set1. Since nums2 is in sorted order, the first common element we find is the minimum common element.

Algorithm:

1. Initialize a set set1, and add the elements from nums1.
2. For each num in nums2:
   1. If num is in set1, return num. We found a common element. Since num2 is sorted in ascending order, the first common element is the minimum common element.
3. Return -1 if there are no common elements.

Code:

class Solution {
public:
    int getCommon(vector<int>& nums1, vector<int>& nums2) {
        // Add the elements from nums1 to set1
        unordered_set<int> set1(nums1.begin(), nums1.end());

        // Search for each element of nums2 in set1
        // Return the first common element found
        for (int num : nums2) {
            if (set1.contains(num)) {
                return num;
            }
        }

        // Return -1 if there are no common elements
        return -1;
    }
};

Complexity Analysis:

Time Complexity: O(n + m), where n be the length of nums1 and m be the length of nums2.

• Creating set1 takes O(n)
• We search for each element of nums2 in set1. Searching for an element in hash set takes O(1) on average, so the time complexity of this step is O(m).
• Total time complexity will be O(n + m).

Space Complexity: O(n)

• We initialize the set set1, which is size O(e) where e is the number of distinct elements in nums1. At worst, there can be n distinct elements, so the space complexity is O(n). 

Approach 2 (Two Pointers)

Intuition:

The intuition behind this problem lies in exploiting the fact that the arrays are sorted. The first common value we find when traversing both arrays left to right is the minimum common value. We can use two pointers to traverse both arrays simultaneously without a nested loop.

Algorithm:

1. Initialize two pointers, i and j, pointing to the beginning of nums1 and nums2 respectively.
2. Iterate through both arrays simultaneously until either of the arrays is exhausted.
3. At each iteration:
   1. Compare the elements pointed to by nums1[i] and nums2[j].
   2. If they are equal, return the common integer found.
   3. If nums1[i] is less than nums2[j], increment i.
   4. If nums1[i] is greater than nums2[j], increment j.
4. If no common integer is found after traversing both arrays, return -1.

Code:

#include <bits/stdc++.h>

int findMinCommon(std::vector<int>& nums1, std::vector<int>& nums2) {
    int i = 0, j = 0;
    while (i < nums1.size() && j < nums2.size()) {
        if (nums1[i] == nums2[j]) {
            return nums1[i];
        } else if (nums1[i] < nums2[j]) {
            i++;
        } else {
            j++;
        }
    }
    return -1; // If no common integer found
}

int main() {
    // Example usage
    std::vector<int> nums1 = {1, 2, 3, 4, 5};
    std::vector<int> nums2 = {2, 4, 6, 8, 10};
    int minCommon = findMinCommon(nums1, nums2);
    if (minCommon != -1) {
        std::cout << "Minimum common integer: " << minCommon << std::endl;
    } else {
        std::cout << "No common integer found." << std::endl;
    }
    return 0;
}

Complexity Analysis:

Time Complexity: O(n+ m), where n be the length of nums1 and m be the length of nums2.

• Since we are iterating through both arrays simultaneously until we find a common integer or exhaust one of the arrays.

Space Complexity: O(1)

• The algorithm uses only a constant amount of extra space..

Approach 3: Binary Search

Intuition:

To arrays are sorted, which means we can utilize binary search.

Binary search uses three pointers. We can call them left, mid, and right.

Initially, left points to the first index of the array and right points to the last. At each step, we calculate mid as the middle element between left and right.

Binary search compares the target value with the middle element at each iteration.

• If the target value is equal to the middle element, the target has been found.
• If the target value is less than the middle element continue to search in the left half.
• If the target value is greater than the middle element, continue to search in the right half.

With every iteration, the search window is divided in half, and the search is continued in either the right or the left side until either the target is found or left becomes greater than right.

We can solve the problem by iterating though each element in nums1, and using binary search to find that element in nums2. We want to perform binary search on the longer array, which will make the algorithm more efficient, so if nums1 is longer, we swap the arrays.

Algorithm:

mid, the middle of the subarray, is set to the index in the middle of the array. The basic midpoint formula is (left + right) / 2.
You'll notice that the below implementations instead use left + (right - left) / 2. This is because if left + right is greater than the maximum integer value, 2^(31)−1, it overflows and causes errors.

left + (right - left) / 2 is an equivalent formula, and never stores a value larger than left or right. Thus, if left and right are within the integer limits, we will never overflow.

1. Declare a function binarySearch that takes an array nums and a target value as parameters and returns true if the target is in the array.
   1. Initialize left pointer to 0 and right pointer to nums.length - 1. These represent the first and last indices of the array.
   2. While left is less than or equal to right, iteratively perform a binary search:
      1. Set mid to left + (right - left) / 2, which is the middle of this section of nums. We will compare nums[mid] to target.
      2. If nums[mid] is greater than target, set right to mid - 1, we will continue to search in the left half nums.
      3. If nums[mid] is less than target, set left to mid + 1, we will continue to search in the right half nums.
      4. Otherwise, nums[mid] equals target, return true.
2. If nums1 is longer than nums2, call getCommon with the arrays swapped.
3. Iterate through each num in nums1, using binary search to determine whether that element is in nums2:
   1. If num is found in nums2, we can return num. This is guaranteed to be the minimum common value, because both arrays are sorted.
4. If we did not find any common elements, return -1. There is no common value.

Code:

class Solution {
public:
    int getCommon(vector<int>& nums1, vector<int>& nums2) {
        // Binary search should be done on the larger array
        // If nums1 is longer, call getCommon with the arrays swapped
        if (nums1.size() > nums2.size()) {
            return getCommon(nums2, nums1);
        }

        // Search for each element of nums1 in nums2
        // Return the first common element found
        for (int num : nums1) {
            if (binarySearch(num, nums2)) {
                return num;
            }
        }

        // Return -1 if there are no common elements
        return -1;
    }

private:
    bool binarySearch(int target, vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }
};

Complexity Analysis:

Time Complexity: O(n log m), where n be the length of the shorter array, and m be the length of the longer array.

• We iterate through the shorter array, using binary search to look for each element in the longer array. Binary Search takes O(log m) time to search through m elements, so the overall time complexity is O(n log m).

Space Complexity: O(1)

• No additional data structures that grow with input size.