Table of Contents

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

- Use two loops, one loop finds any one of the elements and the second loop finds the other element in the same way.
- Subtract the indices we get the distance between them.
- 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.

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

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

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

- Update i to j (i = j).
- because, we need start traversing again from where we found the second element.
- In order to find the other pair as given until we get the minimum distance between them.
- 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.

#### Space Complexity

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