Intersection of Two Arrays II || Leetcode Problem Solution

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 of num1 is lesser than the jth element of num2 : In this case, we will increment the value of i by 1 till and go for next iteration.
• The ith element of num1 is greater than the jth element of num2 : 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.