Replace all occurrences of X by Y or add element K in Array for Q queries

Given an empty array A[] & Q queries of two types 1 and 2 represented by queries1 and queries2 respectively, the task is to find the final state of the array. The queries are of the following type:

• If type[i]=1, insert queries1[i] (say K) to the end of the array A. The value of queries2[i] = -1 for this type of query.
• If type[i]=2, replace all occurrences of queries1[i] (say X) with queries2[i] (say Y) in A[].

Examples:

Input: Q = 3, type = [1, 1, 2], queries1 = [1, 2, 1], queries2 = [-1, -1, 2]
Output: A = [2, 2]
Explanation: Initially A[] is empty. 
After 1st query, A = [1]. 
After 2nd query, A = [1, 2]. 
After 3rd query, A = [2, 2].

Input: Q = 5, type = [1, 1, 1, 2, 2], queries1 = [1, 2, 3, 1, 3], queries2 = [-1, -1, -1, 2, 1]
Output: A = [2, 2, 1]
Explanation: Initially A[] is empty. 
After 1st query, A = [1]. After 2nd query, A = [1, 2]. 
After 3rd query, A = [1, 2, 3]. 
After 4th query A = [2, 2, 3]. 
After 5th query, A = [2, 2, 1].

Input: Q=5, type = [1, 1, 1, 2, 2], queries1 = [1, 2, 3, 1, 2], queries2 = [-1, -1, -1, 2, 3]
Output: A = [3, 3, 3]
Explanation: Initially A[] is empty. 
After 1st query, A = [1]. After 2nd query, A = [1, 2]. 
After 3rd query, A = [1, 2, 3]. After 4th query, A = [2, 2, 3]. 
After 5th query, A = [3, 3, 3].

Naive Approach:

The basic way to solve the problem is to iterate through all the queries type, and for each type[i] = 1 add queries1[i] in A else if type[i]=2, find all occurrences of queries1[i] in A and replace it with queries2[i].

Time Complexity: O(Q²)
Auxiliary Space: O(1)

Efficient Approach: The problem can be solved efficiently using Hashing based on the following idea:

Use a map to store indices of the elements in the array. For  all queries of type 2, find the values to be replaced and give those indices to the replaced values.

Follow the steps below to implement the approach:

• Iterate through each query types of types[i] = 1 (for insertion in A) and types[i] = 2 for replacement of queries1[i] with queries2[i] in A.
• For all queries types[i] = 2, if queries1[i] is present in the hashmap, then copy the vector associated to it into queries2[i] and erase whole of queries1[i]. 
• After all the queries are performed, copy all the values of the hashmap back into the original vector A, with use of indices stored in the hashmap (keys stored as elements and vectors associated that stores indices of that element).
• Now the original vector A is updated and is the final state of the array

Below is the implementation for the above approach:

2 2 

Time Complexity: O(Q * K) where K is the maximum size of the vector formed
Auxiliary Space: O(K)