# Minimum Distances

See the original problem on HackerRank.

## Solutions

### Array

The domain is limited to $$10^5$$, so we can waste some memory to keep the last position of a value.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34  #include #include int main() { std::array pos; pos.fill(-1); std::array dist; dist.fill(0x7FFFFFFF); int n; std::cin >> n; for (int i = 0; i != n; ++i) { int a; std::cin >> a; if (pos[a] != -1) { if (dist[a] != -1) { dist[a] = std::min(dist[a], i - pos[a]); } else { dist[a] = i - pos[a]; } } pos[a] = i; } int min = dist; for (int i = 1; i != dist.size(); ++i) { min = std::min(dist[i], min); } std::cout << (min == 0x7FFFFFFF ? -1 : min) << std::endl; } 

### Hash map

We can use a data structure with fast lookup, like an hash map (a dict in python) to keep values as key and positions as values. The complexity is amortized linear, becase the if v in elem_pos is $$O(1)$$ on average.

  1 2 3 4 5 6 7 8 9 10  n = int(input().strip()) A = [int(A_temp) for A_temp in input().strip().split(' ')] elem_pos = {} dist_min = sys.maxsize for p, v in enumerate(A): if v in elem_pos: dist_min = min(dist_min, p - elem_pos[v]) elem_pos[v] = p print((dist_min, -1)[dist_min == sys.maxsize]) 

A similar solution in C++, using std::unordered_map

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19  int N; cin >> N; vector v(N); copy_n(istream_iterator(cin), N, begin(v)); unordered_map distances; int minDist = INT_MAX; for (auto i=0; isecond, minDist); } distances[v[i]] = i; } if (minDist == INT_MAX) { minDist = -1; } cout << minDist; 

### Red-Black tree

The std::unordered_map can be replaced by std::map that uses less memory $$O(N)$$ but have a lookup of $$O(log N)$$ complexity. std::map is (normally) implemented as a red-black tree.

### Functional approach

A functional approach in Haskell by Alessandro Pezzato

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  import Data.List (groupBy, sortBy) import Data.List.NonEmpty (nonEmpty) import Data.Function (on) import Data.Ord (comparing) import Data.Maybe (fromMaybe) diffAdjacent xs = zipWith (-) (tail xs) xs minDistance :: [Int] -> Maybe Int minDistance = fmap minimum -- take the minimum, discarding Nothing . nonEmpty -- convert empty lists to Nothing . concatMap diffAdjacent -- calculate differences . (fmap . fmap) fst -- keep only indeces (the first in the pair) . groupBy ((==) on snd) -- group by values . sortBy (comparing snd) -- sort by value (the second in the pair) . zip [0..] -- remember indeces main = do _:a <- fmap read . words <$> getContents print . fromMaybe (-1)$ minDistance a 

Explanation:

• sort by values, remembering indeces
• group by values
• keep only indexes
• calculate differences between each index
• take the minimum

It uses point-free style, composing functions. The Maybe data structure is used to represent a computation that may go wrong. It is converted to an Int by fromMaybe, that takes a default value (-1) to be returned in the case the Maybe is Nothing.

We've worked on this challenge in these gyms: modena  padua  milan  turin