Sponsored
Sponsored
This approach utilizes the fact that both arrays are sorted. Using two pointers, one for each array, we traverse the arrays to find the smallest common value:
Time Complexity: O(n + m), where n and m are the lengths of the two arrays. We only traverse each array once.
Space Complexity: O(1), no additional space is used apart from a few variables.
1#include <iostream>
2#include <vector>
3
4int findMinCommonValue(const std::vector<int>& nums1, const std::vector<int>& nums2) {
5 int i = 0, j = 0;
6 while (i < nums1.size() && j < nums2.size()) {
7 if (nums1[i] == nums2[j]) {
8 return nums1[i];
9 } else if (nums1[i] < nums2[j]) {
10 ++i;
11 } else {
12 ++j;
13 }
14 }
return -1;
}
int main() {
std::vector<int> nums1 = {1, 2, 3};
std::vector<int> nums2 = {2, 4};
std::cout << findMinCommonValue(nums1, nums2) << std::endl;
return 0;
}This C++ implementation uses similar logic as the C implementation, utilizing two pointers to traverse through each array to find the smallest common element, which is returned. The beauty here is leveraging C++ STL to handle vectors.
This approach uses a HashSet to store the elements of the smaller array, providing a quick way to check for common elements:
Time Complexity: O(n log n + m), mainly due to qsort and possibly bsearch in the worst case scenario per element in the second array.
Space Complexity: O(n), additional space used for sorting elements.
The JavaScript solution leverages the Set object for fast membership checks. Elements from one list are inserted into a Set and checked against the second list for common occurrence.