Problem: You are given an array and two elements, find the minimum distance between the elements in the array. The array may have duplicates.
For example, if the array is (1, 5, 3, 7, 2, 8, 3, 4, 5, 9, 9, 3, 1, 3, 2, 9)
Min Distance (4, 7): 4
Min Distance (9, 3): 1
Solution: This problem can be solved using two index trackers. The idea is to loop through the array and keep track of the indices of elements that have the same values with the inputs. At the same time, calculate the distance between those two indices and keep the smallest distance.
int minDistance(int *input, int n1, int n2, int length) { int pos1 = INT_MAX; int pos2 = INT_MAX; int distance = length+1; int newDistance; pos1 = pos2 = distance = length; for (int i = 0; i < length; i++) { if (input[i] == n1) pos1 = i; else if (input[i] == n2) pos2 = i; if (pos1 < length && pos2 < length) { newDistance = abs(pos1 - pos2); if (distance > newDistance) distance = newDistance; } } return distance == length+1 ? -1 : distance; } int main() { int arr[] ={13, 5, 4, 2, 6, 3, 9, 4, 8, 3}; int n = sizeof(arr)/sizeof(arr[0]); int x = 5; int y = 6; printf("Minimum distance between %d and %d is %d\n", x, y, minDistance(arr, x, y, n)); return 0; }
Time Complexity: O(N)
This approach is not 100% correct. It is good for test case which does not have duplicates. If array is (1, 5, 3, 7, 2, 8, 3, 4, 5, 9, 9, 3, 1, 3, 2, 9) ,
then min_distance(9,9) should be zero but this approach will provide answer 16.
just a simple modification
Hi mukul,
Can you specify the modification required?
From Lines 11 to 14 ,
if (input[i] == n1)
pos1 = i;
else if (input[i] == n2)
pos2 = i;
if both inputs n1 and n2 are same we always execute only if case
so pos2 will always max value which is length and at the end we return distance which is initialized to length.
just removing the else it will fix the issue
if (input[i] == n1)
pos1 = i;
if (input[i] == n2)
pos2 = i;
other approach will be we can have for inputs if both n1 == n2 then return 0.
Next..
min_dist between 9,9 should be 1 not zero so this will not work.. even if 2, 9′s are far away. it will return 0, right? that’s is not correct.
public static int minDistance(int a[], int n1, int n2){
int pos1 = -1;
int pos2 = -1;
int distance = 100;
int length = a.length;
int newDistance = 0;
int gotDupFlag = 0;
for (int i = 0; i newDistance)
distance = newDistance;
}
}
return distance == 0 ? -1 : distance;
}
def minDistance(array, length,no1,no2):
distance = length + 1
fstpos = length + 1
sndpos = length + 1
for count in range(length):
if no1 == array[count]:
if no1 != no2:
fstpos = count
else:
if fstpos == (length + 1) or (sndpos != (length + 1) and fstpos < sndpos):
fstpos = count
else:
sndpos = count
elif no2 == array[count]:
sndpos = count
if fstpos < (length + 1) and sndpos sndpos:
tempdst = fstpos – sndpos
if sndpos > fstpos:
tempdst = sndpos – fstpos
if tempdst < distance:
distance = tempdst
return distance
***if fstpos == (length + 1) or (sndpos != (length + 1) and fstpos < sndpos):
instead of ***if fstpos < (length + 1) and sndpos sndpos:
in above code
#include
#include
int minDist(int arr[], int n, int x, int y)
{
int i = 0;
int min_dist = INT_MAX;
int prev;
for (i = 0; i < n; i++)
{
if (arr[i] == x || arr[i] == y)
{
prev = i;
break;
}
}
i=i+1;
// Traverse after the first occurence
for ( ; i < n; i++)
{
if (arr[i] == x || arr[i] == y)
{
if ( x!=y&&arr[prev] != arr[i] && (i – prev) < min_dist || x==y&&(i – prev) < min_dist&&arr[prev] == arr[i] )
{
min_dist = i – prev;
prev = i;
}
else{
prev = i;
}
}
}
return min_dist;
}
int main()
{
int arr[] ={9,3,8,2,7,9,1,3,9,5,8,2,3,4};
int n = sizeof(arr)/sizeof(arr[0]);
int x = 9;
int y = 9;
printf("Minimum distance between %d and %d is %d\n", x, y,
minDist(arr, n, x, y));
return 0;
}
//This Solution works for (9,9) ,Duplicate as wells as original examples
#include
#include
using namespace std;
int minDistance(int *input, int n1, int n2, int length)
{
int pos1 = INT_MAX;
int pos2 = INT_MAX;
int distance = length+1;
int newDistance;
pos1 = pos2 = distance = length;
bool flag = false;
for (int i = 0; i < length; i++)
{
if (input[i] == n1 && !flag)
pos1 = i;
else if (input[i] == n2)
pos2 = i;
if (pos1 < length && pos2 newDistance)
distance = newDistance;
} else {
if (pos1 < length)
flag = true;
}
}
return distance == length+1 ? -1 : distance;
}
int main()
{
//int arr[] ={13, 5, 4, 2, 6, 3, 9, 4, 8, 3};
int arr[] = {1, 5, 3, 7, 2, 8, 3, 4, 5, 9, 9, 3, 1, 3, 2, 9};
int n = sizeof(arr)/sizeof(arr[0]);
//int x = 5;
//int y = 6;
int x = 9;
int y = 9;
printf("Minimum distance between %d and %d is %d\n", x, y,
minDistance(arr, x, y, n));
return 0;
}
arr=[1,5,3, 7, 2, 8, 3, 4, 5, 9, 9, 3, 1, 3, 2, 9]
element1=9
element2=9
mindi=len(arr)
for i in range(len(arr)):
if(arr[i]==element1 or arr[i]==element2):
if(arr[i]==element2):
for j in range(i+1,len(arr)):
if(arr[j]==element1):
diff=j-i
if(diff<mindi):
mindi=diff
else:
for j in range(i+1,len(arr)):
if(arr[j]==element2):
diff=j-i
if(diff<mindi):
mindi=diff
print mindi
#include
#include
#include
#define N 16
#define INT_MAX 65536
/*
To find minimum distance between two array elements given in input
*/
int main(void)
{
int a[N]={1,5,3,7,2,8,3,4,5,9,9,3,1,3,2,9};
int x;
int y;
int pos_x,pos_y;
int i=0;
int ans=INT_MAX;
int diff=0;
pos_x=pos_y=-1;
x=9;y=3;
for (i=0;i<N;i++)
{
if (a[i]==x)
{
pos_x=i;
}
else if (a[i]==y)
{
pos_y=i;
}
if (pos_x != -1 && pos_y != -1)
{
diff=pos_x – pos_y;
if (diff diff) ans=diff;
}
}
printf(“Minium difference %d”, diff);
return 0;
}
Correcting
printf(“Minium difference %d”, diff);