Find the Minimum Distance Between Two Numbers

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)

12 Thoughts on “Find the Minimum Distance Between Two Numbers

  1. Mukul Kumar on October 20, 2013 at 2:07 am said:

    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 :P

  2. crazyadmin on October 22, 2013 at 12:47 pm said:

    Hi mukul,

    Can you specify the modification required?

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

    • crazyadmin on October 28, 2013 at 9:02 pm said:

      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;

        }

  4. sidhartha on November 16, 2013 at 11:52 pm said:

    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

  5. sidhartha on November 17, 2013 at 12:01 am said:

    ***if fstpos == (length + 1) or (sndpos != (length + 1) and fstpos < sndpos):
    instead of ***if fstpos < (length + 1) and sndpos sndpos:
    in above code

  6. Surbhi on August 18, 2014 at 2:49 pm said:

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

  7. shailesh pandey on September 18, 2014 at 2:04 am said:

    //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;
    }

  8. Mukesh on January 6, 2015 at 12:54 am said:

    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

  9. #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;
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation