Recent Tutorials and Articles
    HackerRank Solution: Minimum Distances
    Published on: 16th July 2016

    This tutorial provides Java and Python solution to "Minimum Distances" problem of Hackerrank.

    Hackerrank Challenge Details


    Problem Statement:

    Consider an array of n integers, A = [a0, a1,...,an-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.

    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.

    Solution Details


    Java Implementation:

    package com.saintech.allprogtutorials.hackerrank.algos;
    
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Scanner;
    
    /**
     * @author Sain Technology Solutions
     * 
     * Solution to Problem - https://www.hackerrank.com/challenges/minimum-distances
     *
     */
    public class MinimumDistances {
    	public static void main(String[] args) {
    		final Scanner in = new Scanner(System.in);
            int N = in.nextInt();
            
            final Map<Integer, Integer> numDistances = new HashMap<>();
            
            int minDistance = N;
            for(int i=0; i < N; i++){
                final int number = in.nextInt();
                int distance = i;
                
                // if number is found in map, we have found the match. 
                // We calculate the difference and compare it with minDistance
                if(numDistances.containsKey(number)) {
                	distance = Math.abs(i - numDistances.get(number));
                	if(distance < minDistance) {
                		minDistance = distance;
                	}
                }
                numDistances.put(number, distance);
            }
            
            //If minDistance is not updated, it means no pairs were found so we return -1, else minDistance
            System.out.println((minDistance == N) ? -1 : minDistance);
            
            in.close();
    	}
    }

    Thank you for reading through the tutorial. In case of any feedback/questions/concerns, you can communicate same to us through your comments and we shall get back to you as soon as possible.

    Published on: 16th July 2016