Find the minimum distance between two numbers - GeeksforGeeks

Find the minimum distance between two numbers - GeeksforGeeks
Given an unsorted array arr[] and two numbers x and y, find the minimum distance between x and y in arr[]. The array might also contain duplicates. You may assume that both x and y are different and present in arr[].
Input: arr[] = {2, 5, 3, 5, 4, 4, 2, 3}, x = 3, y = 2
Output: Minimum distance between 3 and 2 is 1.

Scan array and maintain some properties.
O(N)
1) Traverse array from left side and stop if either x or y are found. Store index of this first occurrrence in a variable say prev
2) Now traverse arr[] after the index prev. If the element at current index i matches with either x or y then check if it is different from arr[prev]. If it is different then update the minimum distance if needed. If it is same then update prev i.e., make prev = i.

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;

}

O(N^2)

int minDist(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;

}

Linkedin Interview - Shortest distance between two words

This class will be given a list of words (such as might be tokenized
 * from a paragraph of text), and will provide a method that takes two
 * words and returns the shortest distance (in words) between those two
 * words in the provided text. 

1. public int findShortestDist(String[] words, String wordA, String wordB) {  
2.     int n = words.length;  
3.     int dist = n;  
4.     int posA = -1, posB = -1;  
5.     for(int i=0; i<n; i++) {  
6.         if(words[i].equals(wordA)) {  
7.             posA = i;  
8.             if(posB != -1) {  
9.                 dist = Math.min(dist, posA-posB);  
10.             }  
11.         } else if(words[i].equals(wordB)) {  
12.             posB = i;  
13.             if(posA != -1) {  
14.                 dist = Math.min(dist, posB-posA);  
15.             }  
16.         }  
17.     }  
18.     return (posA == -1 || posB == -1) ? -1 : dist;  
19. } 

1. public int findShortestDist(String[] words, String wordA, String wordB) {  
2.     int n = words.length;  
3.     int dist = n+1;  
4.     int posA = -1, posB = -1;  
5.     for(int i=0; i<n; i++) {  
6.         if(words[i].equals(wordA)) {  
7.             posA = i;  
8.         } else if(words[i].equals(wordB)) {  
9.             posB = i;  
10.         }  
11.         if(posA != -1 && posB != -1) {  
12.             dist = Math.min(dist, Math.abs(posA-posB));  
13.         }  
14.     }  
15.     return dist > n ? -1 : dist;  
16. } 

http://www.careercup.com/question?id=5725709041401856
JavaScript Code: http://codesam.blogspot.com/2011/07/minimun-distance-between-two-elements.html

Read full article from Find the minimum distance between two numbers - GeeksforGeeks