HackerRank Minimum Distances Problem Solution

In this post, we will solve HackerRank Minimum Distances Problem Solution.

The distance between two array values is the number of indices between them. Given a find the minimum distance between any pair of equal elements in the array. If no such value exists, return -1.
Example
a = [3, 2, 1, 2, 3]
There are two matching pairs of values: 3 and 2. The indices of the 3’s are i=0 and j = 4, so their distance is d[i, j] = |j — i| = 4. The indices of the 2’s are i = 1 and j = 3, so their distance is d[i, j] = |ji| = 2. The minimum distance is 2.

Function Description

Complete the minimumDistances function in the editor below.

minimumDistances has the following parameter(s):

int a[n]: an array of integers

Returns

int: the minimum distance found or -1 if there are no matching elements

Input Format
The first line contains an integer n, the size of array a. The second line contains n space-separated integers a[i].

Output Format
Print a single integer denoting the minimum d[i, j] in a. If no such value exists, print -1.

Sample Input

STDIN           Function
-----           --------
6               arr[] size n = 6
7 1 3 4 1 7     arr = [7, 1, 3, 4, 1, 7]

Sample Output

Explanation
There are two pairs to consider:

a[1] and @[4] are both 1, so d[1, 4] = |1 — 4 = 3.
a[0] and @[5] are both 7, so d[0, 5] = 10-5 = 5.

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

Table of Contents

Minimum Distances C Solution

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int main(){
    int n; 
    scanf("%d",&n);
    int *A = malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++){
       scanf("%d",&A[i]);
    }
    
    int i, j;
    int distance = n;
    
    for(i=0; i<n-1; i++)
        for(j=i+1; j<n; j++)
        {
            if(A[i]==A[j])
            {
                distance = (distance<(j-i))?distance:(j-i);
            }
        }
    if(distance == n)
        distance = -1;
    printf("%d\n", distance);
    return 0;
}

Minimum Distances C++ Solution

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;


int main(){
    int n;
    cin >> n;
    vector<int> A(n);
    for(int i = 0;i < n;i++){
        cin >> A[i];
    }
    int result = -1;
    for(int i = 0; i < n - 1; i++){
        for(int j = i + 1; j < n; j++){
            if(A[j] == A[i]){
                int dist = j - i;
                if(result == -1 || dist < result){
                    result = dist;
                }
                break;
            }
        }
    }
    cout << result << endl;
    return 0;
}

Minimum Distances C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {

    static void Main(String[] args) {
        int n = Convert.ToInt32(Console.ReadLine());
        string[] A_temp = Console.ReadLine().Split(' ');
        int[] A = Array.ConvertAll(A_temp,Int32.Parse);
        
        	Console.WriteLine(minDistance(n, A));
    }
    public static object minDistance(int n, int[] arr)
	{
		if ((n < 1 | n > 1000))
			return -1;

		int dist = 0;
		List<int> distances = new List<int>();

		for (int i = 0; i <= n - 1; i++) {
			  int cur = arr[i];
			if ((cur < 1 | cur > 100000))
				return -1;

			int curPos = i;
			for (int j = i + 1; j <= n - 1; j++) {
				if (arr[j] == cur) {
					dist = j - curPos;

					distances.Add(dist);
				}
			}
		}

		if (distances.Count == 0)
			return -1;
		  return distances.Min();

	}
}

Minimum Distances Java Solution

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'minimumDistances' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts INTEGER_ARRAY a as parameter.
     */

    public static int minimumDistances(List<Integer> a) {
             HashMap<Integer, Integer> nums =  new  HashMap<Integer, Integer>();

        nums.put(a.get(0), 0);
        int min = Integer.MAX_VALUE;
        boolean f =false;
        for(int i = 1; i < a.size(); i++){
            if(nums.containsKey(a.get(i))){
                nums.put(a.get(i), i - nums.get(a.get(i)));
                f = true;
                if( nums.get(a.get(i)) < min){
                    min = nums.get(a.get(i));
                }
            }else{
                nums.put(a.get(i), i);
            }
        }
        if(!f)
            return -1;
        return min;
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int n = Integer.parseInt(bufferedReader.readLine().trim());

        List<Integer> a = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
            .map(Integer::parseInt)
            .collect(toList());

        int result = Result.minimumDistances(a);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedReader.close();
        bufferedWriter.close();
    }
}

Minimum Distances JavaScript Solution

process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("\n");
    main();    
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////

function main() {
    var n = parseInt(readLine());
    A = readLine().split(' ');
    A = A.map(Number);
    
    var B = A.map(function (val, index) {
        return {value: val, index: index};
    });
    
    B.sort(function(obj1, obj2) {
        var diff = obj1.value - obj2.value;
        if (diff != 0) {
            return diff;
        }
        return obj1.index - obj2.index;
    });
    
    var minDistance = -1;
    
    for (var i = 1; i < B.length; i++) {
        if (B[i].value == B[i - 1].value) {
            var distance = B[i].index - B[i - 1].index;
            if (minDistance == -1) {
                minDistance = distance;
            } else if (distance < minDistance) {
                minDistance = distance;
            }
        }
    }
    
    console.log(minDistance);
    
    //B.forEach(function(obj) { console.log(obj.value + " " + obj.index)} );

}

Minimum Distances Python Solution

n = int(input())
a = [int(_) for _ in input().split()]
b = {}
ans = n
for i in range(n):
    if a[i] in b:
        ans = min(ans, i - b[a[i]])
    b[a[i]] = i
    
if ans == n:
    print(-1)
else:
    print(ans)