# 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;
}
}
``````
POPULAR ONLINE

XML File

188

### 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

### no suitable constructor found for AMStartedEvent(ApplicationAttemptId,long,ContainerId,String,int,int)

i am facing this issuecan anybody please solve it

222

### 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