Minimum Index Distance

See the original problem on HackerRank.

Given two arrays, A and B, of size N that both contain permutations of the same set of unique integers, find and print the number having the absolute minimum index difference between the two arrays. In the event of a tie, choose the smallest number.

Input Format

The first line contains an integer, N, denoting the size of the array. The second line contains N space-separated integers describing array A (a0, a1, …). The third line contains N space-separated integers describing array B (b0, b1, …).

Contraints

 1 2  1 <= N <= 2000 -10^4 <= ai, bi <= 10^4

Output Format

Print the number having the absolute minimum index difference between the two arrays. In the event of a tie, choose the smallest number.

Example

Input:

 1 2 3  6 9 5 1 21 32 8 21 32 9 8 5 1

Output:

 1  8

Explanation:

The absolute difference between the indices for each number are as follows:

 1 2 3 4 5 6  9 = a0 = b2: |0 - 2| = 2 5 = a1 = b4: |1 - 4| = 3 1 = a2 = b5: |1 - 5| = 4 21 = a3 = b0: |3 - 0| = 3 32 = a4 = b1: |4 - 1| = 3 8 = a5 = b3: |5 - 3| = 2

As you can see, the minimum index difference is 2 and there are two numbers, 8 and 9, having this minimum index difference. Since 8 is smaller, we print 8.

Solutions

We can store distances into a sorted map. First, we set distance of element $$i$$ as the index of $$i$$ in the first array - it’s like a baseline.

Afterwards, we read the second array and update the distances by subtracting the index in the map with the current index in the second array.

Finally, we calculate the minimum value. Since the map is sorted, the first minimum retrieved is also the smallest one.

Here is an idea in C++:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  int n; cin >> n; map d; int i; for (auto j=0; j> i; d[i] = j; } for (auto j=0; j> i; d[i] = abs(d[i]-j); } auto minIt = min_element(begin(d), end(d), [](const auto& p1, const auto& p2) { return p1.second < p2.second; }); cout << minIt->first; 
We've worked on this challenge in these gyms: modena