Thursday, January 5, 2012

Minimum Distance Between Two Elements in an Array

Question: 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 (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: 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));
}

Reactions:

0 comments:

Post a Comment