Problem: Minimum Distances

*Difficulty: Easy

Problem:

Consider an array of n integers, A = [a0,a1,…,a(n-1)] . The distance between two indices,i  and j, is denoted by di,j = |i-j|.

Given A, find the minimum di,j such that ai = aj  and i != j . In other words, find the minimum distance between any pair of equal elements in the array. If no such value exists, print -1.

Note: |a| denotes the absolute value of a.

Input Format

The first line contains an integer, n , denoting the size of array A.
The second line contains n  space-separated integers describing the respective elements in array A.

Constraints

1 <= n <= 10^3
1 <= ai <= 10^5

Output Format

Print a single integer denoting the minimum di,j in A; if no such value exists, print -1 .

Sample Input

6
7 1 3 4 1 7

Sample Output

3

Explanation
Here, we have two options:

  •  a1 and a4 are both 1, so d1,4  = |1-4| = 3 .
  •  a0 and a5 are both 7, so d0,5   = |0-5| = 5.

The answer is min(3,5) = 3.

How to solve: 

First create a dictionary store the input order of ai, if the next input a(i+k) = ai, then the distance will be k, and the new position of ai will be i + k.
Here is the step by step running:

pos = [-1,-1,-1,-1,-1,-1,-1,-1] (size of this array equal max(A)+1), or 10^5 + 1, because maximum of ai is 10^5
A = [7,1,3,4,1,7]
min_dis = len(pos) , or 10^3 if you want, because the maximum size of A will be 10^3

a0 = 7
pos = [-1,-1,-1,-1,-1,-1,-1,0] (input order of 7 is 0)

a1 = 1
pos = [-1,1,-1,-1,-1,-1,-1,0]

a2 = 3
pos = [-1,1,-1,2,-1,-1,-1,0]

a3 = 4
pos = [-1,1,-1,2,3,-1,-1,0]

a4 = 1, pos[1] = 1 => distance = 4-1 = 3 , update: pos[1] = 4

a5 = 7, pos[7] = 0 => distance = 5-0 = 5, update: pos[7] = 5

Implementation in Python2:

Screen Shot 2016-07-16 at 1.20.00 PM

Advertisements