Distance between two numbers in an unsorted array

319
December 03, 2017, at 10:25 PM

I am trying to solve this array problem from geeksforgeeks.
Input: arr[] = {1, 2}, x = 1, y = 2
Output: Minimum distance between 1 and 2 is 1.

Input: arr[] = {3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3}, x = 3, y = 6
Output: Minimum distance between 3 and 6 is 4.
Original Problem - Find the distance between two given number in an array such that the distance is minimum.
I am able to solve this problem in O(N).
Now I found same problem in some other challenge with the following modification
Array is circular that mean last element points to first one, Imagine this as a round table and number are student from different universities sitting. **.
Still unclear see the example
**Eg.
7,1,4,3,1,6,7,6,5,2
is the input array and distance is queried for (1,2) then
According to the original problem -> ans is 5(distance between 4th index and 9th index)
According to modified problem -> ans is 2(distance between 9th index and 1st index as first element is connected to last)

Now coming to the issue, I solved the problem with my own approach which works in O(N) + some more comparison.
Can anybody suggest the better approach to this problem.

My Solution

public class MinimumDistanceInArray {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();
        int array[] = new int[N];
        for (int i = 0; i < N; i++) {
            array[i] = s.nextInt();
        }
        int Q = s.nextInt();
        for (int i = 0; i < Q; i++) {
            int first = s.nextInt();
            int second = s.nextInt();
            System.out.println(getMinimumDistance(array, first, second));
        }
        s.close();
    }
    private static int getMinimumDistance(int[] array, int first, int second) {
        int firstIndex = Integer.MAX_VALUE, secondIndex = Integer.MAX_VALUE, minDistance = Integer.MAX_VALUE;
        int firstMinIndex=Integer.MAX_VALUE,firstMaxIndex=Integer.MAX_VALUE,secondMinIndex=Integer.MAX_VALUE,secondMaxIndex=Integer.MAX_VALUE;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == first) {
                firstIndex = i;
                if(firstMinIndex == Integer.MAX_VALUE)
                    firstMinIndex = i;
            }
            if (array[i] == second) {
                secondIndex = i;
                if(secondMinIndex == Integer.MAX_VALUE)
                    secondMinIndex = i;
            }
            if (firstIndex != Integer.MAX_VALUE && secondIndex != Integer.MAX_VALUE) {
                int tempDistance = Math.abs(firstIndex - secondIndex);
                if (tempDistance < minDistance) {
                    if (tempDistance == 0)
                        return 0;
                    minDistance = tempDistance;
                }
            }
        }
        firstMaxIndex = firstIndex;
        secondMaxIndex = secondIndex;
        // first min & second max
        int bigger = firstMinIndex > secondMaxIndex ? firstMinIndex : secondMaxIndex;
        int smaller = firstMinIndex > secondMaxIndex ? secondMaxIndex : firstMinIndex  ;
        int temp = array.length - bigger + smaller;
        // second min & firstmax
        int bigger2 = secondMinIndex > firstMaxIndex ? secondMinIndex : firstMaxIndex;
        int smaller2 =secondMinIndex > firstMaxIndex ? firstMaxIndex: secondMinIndex ;
        int temp2 = array.length - bigger2 + smaller2;
        //System.out.println(temp+" " + temp2);
        if(temp < temp2 && temp < minDistance)
            minDistance = temp;
        if(temp > temp2 && temp2 < minDistance)
            minDistance = temp2;
        return minDistance;
    }
}
Rent Charter Buses Company
READ ALSO
NumberFormatException while converting a string to an integer value in java

NumberFormatException while converting a string to an integer value in java

When I'm trying to parse the input1 string to an integer value it's rising a NumberFormatExceptionI've tried replacing the spaces if any in the string but it didn't work for me

279
read multiple variables with scanner in one line

read multiple variables with scanner in one line

I am trying to read multiple variables from the console with the scanner in only one line (separated with a blank space)

294