Problem Statement
Given two integer arrays nums1
and nums2
, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.
Sample Input
nums1
= [1,2,2,1], nums2
= [2,2]
Sample Output
[2,2]
Link to question: https://leetcode.com/problems/intersection-of-two-arrays-ii/description/
Solution
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
vector<int> result;
int i, j, n1, n2;
n1=nums1.size();
n2=nums2.size();
i=0;
j=0;
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
while(i<n1 && j<n2) {
if(nums1[i]==nums2[j]) {
result.push_back(nums1[i]);
i++;
j++;
}
else if(nums1[i]>nums2[j])
j++;
else
i++;
}
return result;
}
};
Explanation
It is given in the problem statement that we can give the result in any order. And this had made our task easy. Now we can simply sort both the arrays and traverse through them to get our desired result.
We can use two different variables (i and j in this case) to traverse both the arrays. Using the condition i<n1 && j<n2
in while loop, eliminates the need of an extra statement to find the array of the shorter length. Now, among i and j reaches the end of the array, will make the condition to evaluate to false
and the loop will terminate.
Inside the loop, we can check if the element at ith
position and jth
position of the num1
and num2
respectively are equal or not. If they are equal, then we get the element for our resultant array. If they are not equal, then there can be two cases:
-
The
ith
element ofnum1
is lesser than thejth
element ofnum2
: In this case, we will increment the value of i by 1 till and go for next iteration. -
The
ith
element ofnum1
is greater than thejth
element ofnum2
: In this case, we will increment the value of j by 1 till and go for next iteration.
In both the cases, we are trying to reach to such position where both the elements are equal so that we can get our next element for the resultant array.
After some iterations, the shorter array will be full traversed. And if any of the array is fully traversed then we can't get more intersecting elements.
Latest comments (0)