Change all occurrences of X by Y or add ingredient Ok in Array for Q queries

Given an empty array A[] & Q queries of two varieties 1 and 2 represented by queries1 and queries2 respectively, the duty is to search out the ultimate state of the array. The queries are of the next kind:

• If kind[i]=1, insert queries1[i] (say Ok) to the tip of the array A. The worth of queries2[i] = -1 for one of these question.
• If kind[i]=2, exchange all occurrences of queries1[i] (say X) with queries2[i] (say Y) in A[].

Examples:

Enter: Q = 3, kind = [1, 1, 2], queries1 = [1, 2, 1], queries2 = [-1, -1, 2]
Output: A = [2, 2]
Rationalization: Initially A[] is empty. 
After 1st question, A = [1]. 
After 2nd question, A = [1, 2]. 
After third question, A = [2, 2].

Enter: Q = 5, kind = [1, 1, 1, 2, 2], queries1 = [1, 2, 3, 1, 3], queries2 = [-1, -1, -1, 2, 1]
Output: A = [2, 2, 1]
Rationalization: Initially A[] is empty. 
After 1st question, A = [1]. After 2nd question, A = [1, 2]. 
After third question, A = [1, 2, 3]. 
After 4th question A = [2, 2, 3]. 
After fifth question, A = [2, 2, 1].

Enter: Q=5, kind = [1, 1, 1, 2, 2], queries1 = [1, 2, 3, 1, 2], queries2 = [-1, -1, -1, 2, 3]
Output: A = [3, 3, 3]
Rationalization: Initially A[] is empty. 
After 1st question, A = [1]. After 2nd question, A = [1, 2]. 
After third question, A = [1, 2, 3]. After 4th question, A = [2, 2, 3]. 
After fifth question, A = [3, 3, 3].

Naive Strategy:

The essential method to resolve the issue is to iterate via all of the queries kind, and for every kind[i] = 1 add queries1[i] in A else if kind[i]=2, discover all occurrences of queries1[i] in A and exchange it with queries2[i].

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

Environment friendly Strategy: The issue may be solved effectively utilizing Hashing primarily based on the next concept:

Use a map to stor indices of the weather within the array. For for all queries of kind 2, discover the values to get replaced and provides these indices to the changed values.

Observe the steps beneath to implement the strategy:

• Iterate via every question varieties of varieties[i] = 1 (for insertion in A) and varieties[i] = 2 for alternative of queries1[i] with queries2[i] in A.
• For all queries varieties[i] = 2, if queries1[i] is current within the hashmap, then copy the vector related to it into queries2[i] and erase complete of queries1[i]. 
• After all of the queries are carried out, copy all of the values of the hashmap again into the unique vector A, with use of indices saved within the hashmap (keys saved as components and vectors related that shops indices of that ingredient).
• Now the unique vector A is up to date nd is the ultimate state of the array

Beneath is the implementation for the above strategy:

Time Complexity: O(Q * Ok) the place Ok is the utmost dimension of the vector fashioned
Auxiliary House: O(Ok)