Minimum Common Value
Problem
You are given two integer arrays, each sorted in non-decreasing order. Return the smallest integer that appears in both arrays. If the two arrays share no common value, return -1.
nums1 = [1, 2, 3], nums2 = [2, 4]2def get_common(nums1, nums2):
i, j = 0, 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 -1function getCommon(nums1, nums2) {
let i = 0, 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;
}class Solution {
public int getCommon(int[] nums1, int[] nums2) {
int i = 0, 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;
}
}int getCommon(vector<int>& nums1, vector<int>& nums2) {
int i = 0, j = 0;
while (i < (int)nums1.size() && j < (int)nums2.size()) {
if (nums1[i] == nums2[j]) return nums1[i];
if (nums1[i] < nums2[j]) i++;
else j++;
}
return -1;
}Explanation
Both arrays are already sorted, so we can scan them together with two pointers instead of throwing one array into a set. This keeps the extra memory at O(1).
Place i at the start of nums1 and j at the start of nums2. At each step compare the two values they point at. If nums1[i] == nums2[j], we have found a value that lives in both arrays. Because we always moved forward over the smaller numbers first, this is also the smallest shared value — so we return it immediately.
If the values differ, the smaller one can never be matched by anything still ahead in the other array (everything ahead is even larger). So we discard it by advancing its pointer: if nums1[i] < nums2[j] we do i++, otherwise j++.
Example: nums1 = [1, 2, 3], nums2 = [2, 4]. Start with 1 vs 2: since 1 < 2, advance i. Now 2 vs 2: they match, so return 2.
If either pointer runs off the end of its array, there is nothing left to compare, so no common value exists and we return -1.