Two Pointers: Given two arrays find the intersection of two arrays

Problem Statement:

You are given two arrays.

You need to return the intersection of the two arrays and you need to add the duplicate numbers also

Example:

Input:

nums_1 = [1, 2, 2]
nums_2 = [2, 2]

Output: [2, 2]

Solution Explanation:

We will solve the issue with the help of two pointers.

Sort both the arrays.

Take two pointers pointing to the each arrays.

If the elements in num1 is less than the element in num2, increment i

If the elements in num1 is greater than the element in num2, increment j

If both the elements are same, then add in the resultant array

Time Complexity: O(n log n + m log m))
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <string>
#include <climits>

using namespace std;

vector<int> solution(vector<int>& nums1, vector<int>& nums2) 
{
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end());
    
    int i = 0, j = 0;

    vector<int> result;
    
    while (i < nums1.size() && j < nums2.size()) 
    {
        if (nums1[i] < nums2[j]) 
        {
            i++;
        } 
        else if (nums1[i] > nums2[j]) 
        {
            j++;
        } 
        else 
        {
            result.push_back(nums1[i]);
            i++;
            j++;
        }
    }
    
    return result;
}


int main()
{

	vector<int> num1 = {1, 2, 2};
	vector<int> num2 = {2, 2};

    vector<int> res = solution(num1, num2);
  
    for (int i = 0; i < res.size(); i++) 
        cout << res[i] << " ";

    return 0;
}

Output

2 2