The Twin Houses

Easy
0/40
Average time to solve is 20m
profile
Contributed by
14 upvotes
Asked in company
Innovaccer

Problem statement

There are 'N' houses on the left side of the road and 'N' houses on the right side. All of these houses are coloured. The colour of houses on the left and right sides is given by arrays 'A' and 'B', respectively.

Both the arrays 'A' and 'B' are permutations of length 'N'. A permutation of length 'N' is the sequence of length 'N', which consists of all the integers from 1 to 'N' exactly once.

For an 'i-th' house on the left side, you are supposed to find the house on the right side with the same colour as 'A[i]'.

Example : 
'N' = 3, 'A' = {1, 2, 3}, 'B' = {2, 3, 1}.

House 1 on the left side has the same colour as house 3 on the right side.
House 2 on the left side has the same colour as house 1 on the right side.
House 3 on the left side has the same colour as house 2 on the right side.

The answer is {3, 1, 2}.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T', which denotes the number of test cases to be run. Then the test cases follow.

The first line of each test case contains an integer 'N', denoting the number of houses.

The second line contains 'N' space-separated integers denoting the colour of the houses on the left side.

The third line contains 'N' space-separated integers denoting the colour of the houses on the right side.
Output format : 
For each test case, print 'N' space-separated integers denoting the position of the house on the right side with the same colour as 'i-th' house on the left side.

Print the output of each test case in a new line.
Note : 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^5
1 <= A[i], B[i] <= N

All the values in 'A' and 'B' are unique.
Sum of 'N' over all test cases is <= 10^5.

Time Limit: 1 sec
Sample Input 1 :
2
3
1 2 3
3 2 1
2
1 2
1 2
Sample Output 1 :
3 2 1
1 2
Explanation Of Sample Input 1 :
For test 1:
House 1 on the left side has the same colour as house 3 on the right side.
House 2 on the left side has the same colour as house 2 on the right side.
House 3 on the left side has the same colour as house 1 on the right side.

For test 2:
House 1 on the left side has the same colour as house 1 on the right side.
House 2 on the left side has the same colour as house 2 on the right side.
Sample Input 2 :
2
4
4 1 2 3
4 2 1 3
3
2 1 3
1 3 2
Sample Output 2 :
1 3 2 4
3 1 2
Hint

Simulate the problem statement.

Approaches (2)
Brute Force

 

Approach :

 

  • Traverse through the house on the left side.
  • For each house on the left side, find the house of the same colour by iterating through all the houses on the right side.


 

Algorithm:

 

  • Initialise an array 'POSITION' of length 'N' with 0.
  • Loop through the array 'A' from 'i' = 1 to 'i' = 'N' :
    • Loop through the array 'B' from 'j' = 1 to 'j' = 'N' :
      • If 'A[i]' is equal to 'B[j]' :
        • 'POSITION[i]' = 'j'
        • Continue to outer loop
  • Return 'POSITION'.
Time Complexity

O(N ^ 2), where 'N' is the number of houses on one side.

 

Since we are traversing the array 'B' for every element in 'A', hence the overall Time Complexity is O(N ^ 2).

Space Complexity

O(1)

 

We have only used constant extra space. (We don’t count output array in the space complexity of an Algorithm). So, the Space Complexity is constant, i.e. O(1)

Code Solution
(100% EXP penalty)
The Twin Houses
Full screen
Console