Monday, June 15, 2015

Paytm Question: Minimum distance between two numbers in an array

Problem: Given an unsorted array and two numbers num1 and num2, find the minimum distance between num1 and num2 in the given array.

Solution:
  1. Traverse array from start and once either num1 or num2 are found, store the index of this occurrrence in a variable prevIndex.
  2. Going ahead if the number at current index matches with either num1 or num2 then check if it is different from element at prevIndex. If yes, then update the minimum distance if needed. Make prevIndex = current index.

Implementation:

int minDistance(int arr[], int len, int num1, int num2)
{
int minDist = INT_MAX;
int prevIndex = -1;

for(int i = 0; i < len; ++i)
{
if(arr[i] == num1 || arr[i] == num2)
{
if(prevIndex == -1)
prevIndex = i;
else
{
if(arr[i] != arr[prevIndex] && (i - prevIndex) < minDist)
minDist = i - prevIndex;
prevIndex = i;
}
}
}
return minDist;
}

Complexity: O(n)

No comments:

Post a Comment