Leetcode 2540: Minimum Common Value
Given two integer arrays
nums1 and nums2 sorted in non-decreasing order, return the smallest integer that is common to both arrays. If no such integer exists, return -1.Problem
Approach
Steps
Complexity
Input: The input consists of two integer arrays `nums1` and `nums2`, both sorted in non-decreasing order.
Example: nums1 = [10, 15, 20], nums2 = [5, 10, 25]
Constraints:
• 1 <= nums1.length, nums2.length <= 10^5
• 1 <= nums1[i], nums2[j] <= 10^9
Output: The output should be the smallest integer common to both arrays. If no common integer exists, return `-1`.
Example: 10
Constraints:
• The result should be an integer or -1 if no common integer exists.
Goal: To find the smallest integer that is common in both arrays.
Steps:
• Initialize two pointers to traverse the arrays.
• Compare elements of both arrays at the current positions of the pointers.
• If the elements match, return the common element as the result.
• If the element in the first array is smaller, increment the pointer for the first array.
• If the element in the second array is smaller, increment the pointer for the second array.
• If no common elements are found, return -1.
Goal: Ensure that the solution efficiently handles arrays with lengths up to 10^5 and values as large as 10^9.
Steps:
• Both arrays are sorted in non-decreasing order.
• The solution should be efficient in terms of time and space.
Assumptions:
• Both arrays `nums1` and `nums2` are valid and sorted in non-decreasing order.
• The arrays may contain duplicates.
• Input: [4, 7, 9], [5, 7, 8]
• Explanation: The smallest common element between both arrays is 7, so the output is 7.
• Input: [10, 15, 20], [5, 10, 25]
• Explanation: The smallest common element between both arrays is 10, so the output is 10.
Approach: The approach involves using a two-pointer technique to find the smallest common element efficiently.
Observations:
• The arrays are sorted, so we can use a two-pointer technique to compare elements in O(n) time.
• By traversing both arrays and comparing the current elements, we can find the smallest common element efficiently.
Steps:
• Initialize two pointers, one for each array.
• Traverse both arrays and compare the elements at the current pointers.
• If the elements are equal, return that element as the answer.
• If the element in `nums1` is smaller, increment the pointer for `nums1`.
• If the element in `nums2` is smaller, increment the pointer for `nums2`.
• If no common elements are found by the end of the arrays, return -1.
Empty Inputs:
• Both arrays are assumed to be non-empty.
Large Inputs:
• Ensure that the solution works efficiently for large inputs with up to 10^5 elements.
Special Values:
• Handle cases where there are no common elements.
Constraints:
• The solution must be efficient enough to handle the largest possible inputs.
int getCommon(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> mp;
for(int x: nums1)
mp[x] = true;
for(int y: nums2)
if(mp.count(y))
return y;
return -1;
}
1 : Function Definition
int getCommon(vector<int>& nums1, vector<int>& nums2) {
The function 'getCommon' is defined, which takes two vectors 'nums1' and 'nums2' as input and returns the first common element between them, or -1 if no common element is found.
2 : Map Initialization
unordered_map<int, int> mp;
An unordered map 'mp' is initialized to store elements from 'nums1'. The map will help check if any element in 'nums2' is present in 'nums1'.
3 : Loop Through First Array
for(int x: nums1)
A for loop iterates through each element 'x' of the first array 'nums1'.
4 : Map Population
mp[x] = true;
For each element 'x' in 'nums1', it is added to the map 'mp' with the value 'true'. This marks the presence of the element in 'nums1'.
5 : Loop Through Second Array
for(int y: nums2)
A second for loop iterates through each element 'y' in the second array 'nums2'.
6 : Check for Common Element
if(mp.count(y))
This if statement checks whether the element 'y' from 'nums2' exists in the map 'mp'. The count function returns true if the element is present.
7 : Return Common Element
return y;
If a common element 'y' is found, it is immediately returned as the first common element between 'nums1' and 'nums2'.
8 : Return -1
return -1;
If no common element is found after checking all elements of 'nums2', the function returns -1 to indicate there is no common element.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we only traverse each array once using two pointers.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) as we only use a constant amount of extra space for the pointers.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus