Friday, July 8, 2011

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. Here is the implementation in JavaScript:

function nMinDistanceBetweenTwoElements (nInputArray, nNum1, nNum2)
{
   if (nInputArray.length <= 0)
   {
      document.write("Empty Array!");
      return -1;
   }

   var nPos1 = nPos2 = nDis = nInputArray.length;

   for (var i = 0; i < nInputArray.length; i++)
   {
      if (nInputArray[i] == nNum1)
         nPos1 = i;
      else if (nInputArray[i] == nNum2)
         nPos2 = i;

      if (nPos1 < nInputArray.length && nPos2 < nInputArray.length)
      {
         if (nDis > Math.abs(nPos1 - nPos2))
            nDis = Math.abs(nPos1 - nPos2);
      }
   }

   return nDis == nInputArray.length ? -1 : nDis;
}

Code explanation: the method accepts three parameters. nInputArray is an array of integers. nNum1 and nNum2 are the two numbers that we must find the minimum distance between them. Here are the steps in the method:

  1. First, we check for the length of the array. If the client passes in an empty or invalid array, we return -1 and an error message.
  2. Next, we declare three variables. nPos1 and nPos2 keep track of the indices of the first number nNum1 and the second number nNum2 respectively. nDis keeps track of the minimum distance between the two numbers. We also initialize all of these variables to the input array's length because there is a chance that the input array doesn't contain both of the input numbers whose distance we must find. In other words, if the input array doesn't contain any of the two input numbers, nDis will equal the array's length at the end of the method. Moreover, we must also initialize nDis to a large number that is not obtainable by any pair of numbers in the array because we are trying to find the minimum distance. If we initialize nDis to 0, it's more complicated to use nDis to keep track of the minimum distance. nDis = 0 is already the smallest possible distance between any two elements in an array.
  3. The for loop will go through the entire input array ,nInputArray once. At each iteration, we do the following:
    • If the current element, nInputArray[i], equals to the first input number, nNum1, then assign nPos1 to that element's index, i. On the other hand, if the current element's value equals nNum2, then assign nPos2 to that element's index. Otherwise, we do nothing.
    • Next, we check if both of the index trackers' values have changed. If the values of nPos1 and nPos2 are less than the input array's length, it means that nNum1 and nNum2 exist in the input array. Again, we are guarding against the possibility that nNum1 or nNum2 is not in the input array.
    • If nPos1 and nPos2 are less than their initial values, then both nNum1 and nNum2 are present in nInputArray. Thus, we need to find out whether the new distance between nNum1 and nNum2 is less than the current minimum distance, nDis. If the new distance is less than nDis, we change nDis to the new distance. Note that we use the absolute value of the difference between nPos1 and nPos2 to figure out the distance. The reason are that nPos2 may be smaller than nPos1 and that we don't care about the numbers' order.
  4. After the for loop, we check to see whether nDis is different from its initial value which is the input array's length. If nDis equals its initial value, input numbers are not present in the input array. We return -1 as an error indicator. However, if nDis is different from its initial value, both input numbers must be in the input array. Therefore, we return nDis as the minimum distance between those two numbers.

I hope the code and the explanation are clear. However, if you have any question, please let me know by emailing or commenting. Thanks for reading :)

2 comments:

  1. I think, this wont work when there are duplicate element of npos1.

    ReplyDelete
  2. Hi, I've tested the code again with arrays containing duplicates. Everything seems to work. If you have specific input that doesn't work, plz post. Thanks :)

    ReplyDelete