Minimum Distance Between Two Elements in an Array

Question

Given an unsorted array and two elements, find the minimum distance between the elements in the array. The array may have duplicates.

Example
For example, if the
Input array is (2, 1, 3, 4, 0, 2, 5) and the two elements are 4 and 5,
then the min distance is 3 because 4 is at index 3 and 5 is at index 6.

Solution

Method 1 - Brute force
Use two loops: The outer loop picks all the elements of arr[] one by one. The inner loop picks all the elements after the element picked by outer loop. If the elements picked by outer and inner loops have same values as x or y then if needed update the minimum distance calculated so far.

int minDistanceBetweenTwoElements (int arr[], int n, int x, int y)
{
   int i, j;
   int min_dist = INT_MAX;
   for (i = 0; i < n; i++)
   {
     for (j = i+1; j < n; j++)
     {
         if( (x == arr[i] && y == arr[j] ||
              y == arr[i] && x == arr[j]) && min_dist > abs(i-j))
         {
              min_dist = abs(i-j);
         }
     }
   }
   return min_dist;
}

Time complexity - O(n^2)

Method 2 - Keeping the indices of the element occurence
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.

This solution works great because it doesn't compare all possible distances of inputs when there are duplicates in the array. A naive solution would be computing all different distances between elements that have the same values with the inputs and then return the smallest distance.

public static int minDistanceBetweenTwoElements (int[] inputArray, int num1, 
                                                    int num2)
{
   
 int pos1;
 int pos2;
 int distance;
 int newDistance;
    pos1 = pos2 = distance = inputArray.length;

   for (int i = 0; i < inputArray.length; i++)
   {
      if (inputArray[i] == num1)
         pos1 = i;
      else if (inputArray[i] == num2)
         pos2 = i;

      if (pos1 < inputArray.length && pos2 < inputArray.length)
      {
         newDistance = Math.abs(pos1 - pos2);
         if (distance > newDistance)
            distance = newDistance;
      }
   }

   return distance == inputArray.length ? -1 : distance;
}

public static void main(String[] args){
 int arr[] = {2, 1, 3, 4, 0, 2, 5};
 out.println(minDistanceBetweenTwoElements(arr,1,2));
}

We can simplify further by not using 2 position. We can just store the previous occurrence of  either number.

int minDist(int arr[], int n, int x, int y)
{
   int i = 0;
   int min_dist = INT_MAX;
   int prev;
 
   // Find the first occurence of any of the two numbers (x or y)
   // and store the index of this occurence in prev
   for (i = 0; i < n; i++)
   {
     if (arr[i] == x || arr[i] == y)
     {
       prev = i;
       break;
     }
   }
 
   // Traverse after the first occurence
   for ( ; i < n; i++)
   {
      if (arr[i] == x || arr[i] == y)
      {
          // If the current element matches with any of the two then
          // check if current element and prev element are different
          // Also check if this value is smaller than minimm distance so far
          if ( arr[prev] != arr[i] && (i - prev) < min_dist )
          {
             min_dist = i - prev;
             prev = i;
          }
          else
             prev = i;
      }
   }
 
   return min_dist;
}

Time Complexity: O(n)

Reference - http://www.geeksforgeeks.org/find-the-minimum-distance-between-two-numbers/