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.
This Python solution uses Python's set data structure to conveniently test for the presence of elements in constant time. We insert elements of one array into a set and test elements of the other array against it.