Problem Statement

Given two sorted arrays nums1 and nums2 containing integers only, return the smallest integer that appears in both arrays. If there isn't any integer that exists in both arrays, the function should return -1.

Examples

Example 1:

• input: nums1 = [1, 3, 5, 7], nums2 = [3, 4, 5, 6, 8, 10]
• expectedOutput: 3
• Justification: Both arrays share the integers 3 and 5, but the smallest common integer is 3.

Example 2:

• input: nums1 = [2, 4, 6], nums2 = [1, 3, 5]
• expectedOutput: -1
• Justification: There are no integers common to both nums1 and nums2, hence the output is -1.

Example 3:

• input: nums1 = [1, 2, 2, 3], nums2 = [2, 2, 4]
• expectedOutput: 2
• Justification: The integer 2 is the only common number between nums1 and nums2, appearing multiple times in both, and it is the smallest.

Constraints:

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

Solution

To efficiently solve this problem, a binary search algorithm can be employed due to the sorted nature of the input arrays. The binary search approach will be utilized to find the smallest common integer between the two arrays.

We start by iterating through the smaller array and use binary search on the larger array to check for the presence of each element from the smaller array. This ensures that we only search for potential common values and hence minimize the number of comparisons. Using binary search reduces the time complexity significantly compared to a linear search, especially for larger arrays, making this approach both efficient and effective.

Step-by-step Algorithm

1. Swap Arrays if Necessary:

   • If nums1 is longer than nums2, swap them. This ensures that the binary search is always performed on the larger array, optimizing search efficiency.

2. Iterate through the Smaller Array:

   • Loop through each element num in the smaller array (nums1).

3. Binary Search in Larger Array:

   • For each element num, call the binarySearch method on the larger array (nums2).
   • If binarySearch returns True (element found in nums2), immediately return the num as it is the smallest common element found so far.

4. No Common Element Found:

   • If the loop completes without finding any common element, return -1.

5. Binary Search Method:

   • Initialize two pointers, left and right, to define the search boundaries.
   • While left is less than or equal to right:
     • Calculate the middle index mid.
     • Compare the target with the element at mid.
     • Adjust the left or right pointers based on the comparison result to narrow the search.
   • If the target is not found by the end of the loop, return False.

Algorithm Walkthrough

Let's consider the input: nums1 = [1, 3, 5, 7], nums2 = [3, 4, 5, 6, 8, 10]

1. Initial Check:

   • nums1 length is 4 and nums2 length is 6. No need to swap since nums2 is already larger.

2. Binary Search for 1:

   • Initialize left = 0 and right = 5.
   • Calculate the middle index: mid = (0 + 5) // 2 = 2. The element at mid is nums2[2] = 5.
   • Since nums2[2] (5) is greater than 1, adjust the right pointer: right = mid - 1 = 1.
   • Recalculate mid: mid = (0 + 1) // 2 = 0. The element at mid is nums2[0] = 3.
   • Since nums2[0] (3) is greater than 1, adjust the right pointer again: right = mid - 1 = -1.
   • At this point, left = 0 is greater than right = -1, ending the search. The target 1 is not found.

3. Binary Search for 3:

   • Found in nums2.
     • Start: left = 0, right = 5, mid = 2 (nums2[2] = 5).
     • nums2[2] > 3, so adjust right to mid - 1 (right = 1).
     • New mid = 0 (nums2[0] = 3).
     • nums2[0] = 3, found the target. Return 3.

4. Return Value:

   • The smallest common element 3 is returned after the second binary search.