#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;


// Run-time complexity O(n*m)
// Memory complexity O(n)
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {

    // Get size of vector nums1
    int n = nums1.size();

    // Declare result variable
    vector<int> result;

    for (int num1 : nums1) {
        // Iterate over numbers in nums1
        int times = count(nums2.begin(), nums2.end(), num1); //O(m)
        // Count how many of that number there are in nums2
        if (times > 0) {
            // if at least 1, push it
            result.push_back(num1);

            // erase 1
            vector<int>::iterator it = find(nums2.begin(), nums2.end(), num1);
            nums2.erase(it);
        }
       // loop
    }

    return result;
}

// Run-time complexity O(max(nlogn, mlogm))
// Memory complexity O(n)
vector<int> intersect_2(vector<int>& nums1, vector<int>& nums2) {

    vector<int> result;

    if (nums1.empty() || nums2.empty())
        return result;

    int i = 0;
    int j = 0;

    sort(nums1.begin(), nums1.end()); //O(nlogn)
    sort(nums2.begin(), nums2.end()); //O(mlogm)

    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;
}

// Run-time complexity O(max(n, m))
// Memory complexity O(n)
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, int> hashmap;
    vector<int> result;

    if (nums1.empty() || nums2.empty())
        return result;

    for (int num : nums1) {
        ++hashmap[num];
    }

    for (int num : nums2) {
        if (hashmap[num] != 0) {
            result.push_back(num);
            --hashmap[num];
        }
    }

    return result;
}