Thursday, January 5, 2012

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 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 - tricky
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));
}

Time Complexity: O(n)

Reactions:

0 comments:

Post a Comment