Find minimum distance between two numbers in an array

In the given unsorted array, which may also contain duplicates, find the minimum distance between 2 different numbers in the given array.

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

Example

Input array be

Algorithm 1

Time Complexity: O(n^2) , Order is O(n^2) because of the 2 loops.

  1. Use two loops, one loop finds any one of the element and 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.

Algorithm working Example

C++ Program

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int arr[] =  { 3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3}; //array
	int N = sizeof(arr)/sizeof(arr[0]); //size of array
	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;
}
Try It

Algorithm 2

Time Complexity: O(n)

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 size of 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 second element.
  3. In order find the other pair like given until we get minimum distance between them.
  4. So, every time we update the minimum distance by comparing with the new distance until we traverse the entire array.

Step 4: we print the minimum distance finally

Algorithm working Example

C++ Program

 #include <bits/stdc++.h>
using namespace std;

int main()
{
	int arr[] =  { 3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3}; //array
	int N = sizeof(arr)/sizeof(arr[0]); //size of array
	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;
}
Try It


Next > < Prev
Scroll to Top