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<int, int> d;
int i;
for (auto j=0; j<n; ++j)
{
    cin >> i;
    d[i] = j;
}

for (auto j=0; j<n; ++j)
{
    cin >> 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;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


fn minimum_index_differnce(fst: Vec<i32>, snd: Vec<i32>) -> i32 {
    let mut map: BTreeMap<i32, i32> = BTreeMap::new();

    for (i, &v) in fst.iter().enumerate() {
        map.insert(v, i as i32);
    }

    for (i, &v) in snd.iter().enumerate() {
        map.entry(v).and_modify(|x| *x = (*x - i as i32).abs());
    }

    *map.iter().min_by(|(_, lv), (_, rv)| lv.cmp(rv)).unwrap().0
}

Functional approach by Alessandro Pezzato, using zipWith. This higher order function takes two lists and a function, generating a new list where each element is the the result of the function where original elements in the same position are the arguments.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


import Data.Function (on)
import Data.List (minimumBy, sortOn, zipWith)

minIndexDiff :: [[Int]] -> Int
minIndexDiff lists = fst (minimumBy (compare `on` snd) diffs)
  where
    enumerateAndSort ls = sortOn fst (zip ls [0 ..])
    [xs, ys] = fmap enumerateAndSort lists
    diffs = zipWith (\(x, i) (_, j) -> (x, abs (i - j))) xs ys

main =
  interact
    (show . minIndexDiff . ((fmap . fmap) read) . fmap words . tail . lines)

This is what happens:

original:

1
2


[9,5,1,21,32,8]
[21,32,9,8,5,1]

enumerate both lists:

1
2


[(9,0),(5,1),(1,2),(21,3),(32,4),(8,5)]
[(21,0),(32,1),(9,2),(8,3),(5,4),(1,5)]

sort by value:

1
2


[(1,2),(5,1),(8,5),(9,0),(21,3),(32,4)]
[(1,5),(5,4),(8,3),(9,2),(21,0),(32,1)]

zip with difference

1
2


[(1,3),(5,3),(8,2),(9,2),(21,3),(32,3)]
                ^ minimum

Same approach, but in Rust language:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


fn enumerate_and_sort(vec: Vec<i32>) -> Vec<(i32, i32)> {
    let mut vec: Vec<(usize, &i32)> = vec.iter().enumerate().collect();
    vec.sort_by(|a, b| a.1.cmp(&b.1));
    vec.iter().map(|x| (x.0 as i32, *x.1)).collect()
}

fn minimum_index_differnce(fst: Vec<i32>, snd: Vec<i32>) -> i32 {
    let fst = enumerate_and_sort(fst);
    let snd = enumerate_and_sort(snd);

    *fst.iter()
        .zip(snd.iter())
        .map(|((i, x), (j, _))| (x, (i - j).abs()))
        .min_by(|d1, d2| d1.1.cmp(&d2.1))
        .unwrap()
        .0
}

Python solution by Davide Peron

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14



#!/bin/python3

n = int(input())
a1 = map(int, input().split())
a2 = map(int, input().split())

dict1 = dict(zip(a1, range(n)))
dict2 = dict(zip(a2, range(n)))

distances = { key: abs(dict1[key] - dict2[key]) for key in dict1 }

min_distance = min(distances.values())
print(min(num for num, distance in distances.items() if distance == min_distance))

ad hoc