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 <stdio.h>
2
3int findMinCommonValue(int *nums1, int nums1Size, int *nums2, int nums2Size) {
4 int i
This code uses a two-pointer technique to find the minimum common value. It initializes two pointers at the beginning of both arrays and progresses them based on the comparison of the elements they point to. If an equal element is found on both sides, it is the smallest common element due to sorted nature of arrays, and thus it is returned. If no common element is found until any one pointer reaches the end, -1 is returned.
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.
#include <vector>
#include <unordered_set>
int findMinCommonValue(const std::vector<int>& nums1, const std::vector<int>& nums2) {
std::unordered_set<int> set(nums1.begin(), nums1.end());
for (int num : nums2) {
if (set.find(num) != set.end()) {
return num;
}
}
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;
}In this C++ implementation, we use an unordered_set to store all elements from the smaller array for constant-time lookup. We then iterate over the second array to check directly for the presence of elements in the set.