Minimum Distances · Coding Gym

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 <iostream>
#include <map>

int main() {
  std::array<int, 100001> pos;
  pos.fill(-1);
  std::array<int, 100001> 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[0];
  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<int> v(N);
copy_n(istream_iterator<int>(cin), N, begin(v));
unordered_map<int, int> distances;
int minDist = INT_MAX;
for (auto i=0; i<N; ++i)
{
    auto it = distances.find(v[i]);
    if (it != end(distances))
    {
        minDist = min(i-it->second, 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.

hashtable