Two Pointers: Given 2 arrays, find the common elements

Problem Statement:

You are given 2 arrays.

You need to return the common elements between the 2 arrays

Example:

Input:

a = [1, 2, 3, 4]
b = [4, 5, 3, 7]

Output:

[3, 4]

Solution 1: Bruteforce approach

In this approach we will use nested for loops to check if the element in the first array is present in the second array.

Time Complexity: O(n*m)
Space Complexity: O(1)

Solution 2: Two pointer approach

In this approach, sort the arrays.

Then check if the element in the first array is smaller then move the first array pointer else move the second array pointer.

Then check if 2 elements are same in both the arrays, then append to the result.

Time Complexity: O(n logm)
Space Complexity: O(1)

Code Solution

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

using namespace std;

vector<int> solution_2 (vector<int>& nums1, vector<int>& nums2) 
{
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end());
    
    vector<int> result;

    int i = 0, j = 0;
    
    while(i < nums1.size() && j < nums2.size()) 
    {
        if(nums1[i] == nums2[j]) 
        {

            result.push_back(nums1[i]);

            i++;
            j++;
        } 
        else if(nums1[i] < nums2[j]) 
        {
            i++;
        } 
        else 
        {
            j++;
        }
    }
    
    return result;
}

vector<int> solution_1 (vector<int>& nums1, vector<int>& nums2) 
{
    vector<int> result;

    for (int i = 0; i < nums1.size(); i++) 
    {   
      	for (int j = 0; j < nums2.size(); j++) 
      	{
            if (nums1[i] == nums2[j]) 
            { 
              	result.push_back(nums1[i]);
              	break;
            }
        }
    }

    return result;
}

int main() 
{
    vector<int> nums1 = {1, 2, 3, 4}; 
    vector<int> nums2 = {4, 5, 3, 7};

    vector<int> res = solution_1(nums1, nums2);
  
    for (int i = 0; i < res.size(); i++) 
        cout << res[i] << " ";

    cout<<endl;

	res = solution_2(nums1, nums2);
  
    for (int i = 0; i < res.size(); i++) 
        cout << res[i] << " ";

    return 0;
}

Output

3 4
3 4