Leetcode 2540. Minimum Common Value
Intuition
Since both arrays are sorted, we can find the minimum common value by iterating from left to right with two pointers.
Approach
Initialize both pointers to 0 to start at the beginning of the array. While both pointers are within bounds of the array, check to see if they are pointing to the same value. If so, we have our answer. If not, increment the smaller value.
Because these arrays are sorted and we started at the beginning I.E. with the smallest values, we know the current smallest values don't match and therefore we must check if the next smallest value does match.
Finally if we get through both arrays without finding a match, return -1 since there is no common value.
Complexity
Time complexity:
O(n)O(n)O(n) since at worst case we would have to go through all nnn values of the arrays.Space complexity:
O(1)O(1)O(1) since we are not using any extra space (besides the pointers).
Code
public class Solution
{
public int GetCommon(int[] nums1, int[] nums2)
{
//create two pointers, one for each array
int num1 = 0;
int num2 = 0;
//loop while both pointers are in range
while(num1 < nums1.Length && num2 < nums2.Length)
{
//if the number at both pointers is the same, we found our result
if(nums1[num1] == nums2[num2])
{
return nums1[num1];
}
//if num1 is smaller, increment it by 1
else if(nums1[num1] < nums2[num2])
{
num1++;
}
//otherwise if num2 is smaller, increment it by 1
else
{
num2++;
}
}
//if end of loop is reached, no result was found
return -1;
}
}