# Find Minimum Distance Between Two Numbers in an Array  Difficulty Level Medium
Frequently asked in Amazon Paytm Uber
Array

## Problem Statement  In the given unsorted array, which may also contain duplicates, find the minimum distance between two different numbers in an array.

Distance between 2 numbers in an array: the absolute difference between the indices +1.

## Example  Input

12

3 5 4 2 6 5 6 6 5 4 8 3

3 6

Output

4

## Approach 1  1. Use two loops, one loop finds any one of the elements and the second loop finds the other element in the same way.
2. Subtract the indices we get the distance between them.
3. Do this until we get the minimum distance.

### Implementation

#### C++ Program for Find Minimum Distance Between Two Numbers in an Array

```#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
int X , Y;
cin>>X>>Y; //the elements between which minimum distance is to be found
int min_dist = INT_MAX;
for(int i=0; i<n; i++) //select one element
{
for(int j=i+1; j<n; j++) //traverse ahead
{
if(arr[i] == X and arr[j] == Y) // if we get X and Y we try to update the minimum distance
min_dist = min(min_dist , abs(i-j));
if(arr[i] == Y and arr[j] == X)
min_dist = min(min_dist , abs(i-j));
}
}
cout<<min_dist;
return 0;
}```

#### Java Program for Find Minimum Distance Between Two Numbers in an Array

```import static java.lang.Math.min;
import java.util.Scanner;

class sum
{
public static int abs(int x)
{
if(x<0)
x=x*-1;
return x;
}
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int arr[] = new int[n];
for(int i=0;i<n;i++)
{
arr[i] = sr.nextInt();
}
int X = sr.nextInt(); int Y = sr.nextInt(); //the elements between which minimum distance is to be found
int min_dist = 10000000;
for(int i=0; i<n; i++) //select one element
{
for(int j=i+1; j<n; j++) //traverse ahead
{
if(arr[i] == X && arr[j] == Y) // if we get X and Y we try to update the minimum distance
min_dist = min(min_dist , abs(i-j));
if(arr[i] == Y && arr[j] == X)
min_dist = min(min_dist , abs(i-j));
}
}
System.out.println(min_dist);
}
}```
```12
3 5 4 2 6 5 6 6 5 4 8 3
3 6```
`4`

### Complexity Analysis

#### Time Complexity

O(n^2) where n is the size of the array. Here we run two-loop one for finding index for x and another for finding index for y. Now for each value find the minimum which each pair of possible value.

Queries for Number of Distinct Elements in a Subarray

#### Space Complexity

O(1) because we don’t use any auxiliary space here.

## Algorithm 2  Step 1: Let i, j be the position where X and Y are there.

1. Initialize i,j with 0.

Step 2: Run a loop such that i and j are less than size of array. If we get any one of the element we simply loop till we get another element.

1. Let the size of the array be N, we got X at j then we loop from j to N.

Step 3: We now update the minimum distance after finding the second element by the difference between the indices.

1. Update i to j (i = j).
2. because, we need start traversing again from where we found the second element.
3. In order to find the other pair as given until we get the minimum distance between them.
4. So, every time we update the minimum distance by comparing it with the new distance until we traverse the entire array.

Step 4: we print the minimum distance finally

### Implementation

#### C++ Program for Find Minimum Distance Between Two Numbers in an Array

```#include <bits/stdc++.h>
using namespace std;
int main()
{
int N;
cin>>N;
int arr[N];
for(int i=0;i<N;i++)
{
cin>>arr[i];
}
int X , Y;
cin>>X>>Y; //the elements between which minimum distance is to be found
int min_dist = INT_MAX;
int i = 0, j = 0; //i and j to point at X and Y present somewhere in the array
while(i < N and j < N)
{
if(arr[i] == X) //if we get X
{
while( j < N and arr[j] != Y) // we simply loop till we get Y
j++;
if(j < N and arr[j] == Y)
min_dist = min(min_dist,abs(i-j));//we update the minimum distance if required

i = j; // important step because as we got X,Y pair we can stand at present position and loop forward for another pair
}
else if(arr[i] == Y)
{
while( j < N and arr[j] != X)
j++;

if(j < N and arr[j] == X)
min_dist = min(min_dist,abs(i-j));
i = j;
}
else
i++;
}
cout<<min_dist;
return 0;
}```

#### Java Program for Find Minimum Distance Between Two Numbers in an Array

```import static java.lang.Math.min;
import java.util.Scanner;

class sum
{
public static int abs(int x)
{
if(x<0)
x=x*-1;
return x;
}
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
int n = sr.nextInt();
int arr[] = new int[n];
for(int i=0;i<n;i++)
{
arr[i] = sr.nextInt();
}
int X = sr.nextInt(); int Y = sr.nextInt(); //the elements between which minimum distance is to be found
int min_dist = 10000000;
int i = 0, j = 0; //i and j to point at X and Y present somewhere in the array
while(i < n && j < n)
{
if(arr[i] == X) //if we get X
{
while( j < n && arr[j] != Y) // we simply loop till we get Y
j++;
if(j < n && arr[j] == Y)
min_dist = min(min_dist,abs(i-j));//we update the minimum distance if required
i = j; // important step because as we got X,Y pair we can stand at present position and loop forward for another pair
}
else if(arr[i] == Y)
{
while( j < n && arr[j] != X)
j++;

if(j < n && arr[j] == X)
min_dist = min(min_dist,abs(i-j));
i = j;
}
else
i++;
}
System.out.println(min_dist);
}
}```
```6
3 5 4 2 5 5
3 5```
`1`

### Complexity Analysis

#### Time Complexity

O(n) where n is the size of the array. Here we use some while loop which runs maximum on n times which leads us to linear time complexity.