POTD Solutions | 02 Nov’ 23 | Minimum distance between two numbers
Welcome to the daily solutions of our PROBLEM OF THE DAY (POTD). We will discuss the entire problem step-by-step and work towards developing an optimized solution. This will not only help you brush up on your concepts of Arrays but will also help you build up problem-solving skills.
POTD 02 November: Minimum Distance between two numbers
You are given an array A[], of n elements. Find the minimum index based distance between two distinct elements of the array, x and y. Return -1, if either x or y does not exist in the array.
Example 1:
Input: N = 4, A[] = {1, 2, 3, 2}, x = 1, y = 2
Output: 1
Explanation: x = 1 and y = 2. There are two distances between x and y, which are 1 and 3 out of which the least is 1.Example 2:
Input: N = 7, A[] = {86, 39, 90, 67, 84, 66, 62}, x = 42, y = 12
Output: –1
Explanation: x = 42 and y = 12. We return -1 as x and y don’t exist in the array.
Minimum Distance Between Two Numbers By Checking Consecutive (x, y) Pairs:
The basic approach is to check only consecutive pairs of x and y. For every element x or y, check the index of the previous occurrence of x or y and if the previous occurring element is not similar to current element update the minimum distance. But a question arises what if an x is preceded by another x and that is preceded by y, then how to get the minimum distance between pairs. By analyzing closely it can be seen that every x followed by y or vice versa can only be the closest pair (minimum distance) so ignore all other pairs.
Below is the implementation of the above approach:
C++
class Solution { public : int minDist( int a[], int n, int x, int y) { // previous index and min distance int p = -1, min_dist = INT_MAX; for ( int i = 0; i < n; i++) { if (a[i] == x || a[i] == y) { // we will check if p is not equal to -1 and // If the element at current index matches // with the element at index p , If yes then // update the minimum distance if needed if (p != -1 && a[i] != a[p]) min_dist = min(min_dist, i - p); // update the previous index p = i; } } // If distance is equal to int max if (min_dist == INT_MAX) return -1; return min_dist; } }; |
Java
class Solution { int minDist( int a[], int n, int x, int y) { // previous index and min distance int i = 0 , p = - 1 , min_dist = Integer.MAX_VALUE; for (i = 0 ; i < n; i++) { if (a[i] == x || a[i] == y) { // we will check if p is not equal to -1 and // If the element at current index matches // with the element at index p , If yes then // update the minimum distance if needed if (p != - 1 && a[i] != a[p]) min_dist = Math.min(min_dist, i - p); // update the previous index p = i; } } // If distance is equal to int max if (min_dist == Integer.MAX_VALUE) return - 1 ; return min_dist; } } |
Python3
class Solution: def minDist( self , arr, n, x, y): # previous index and min distance i = 0 p = - 1 min_dist = 1e6 for i in range (n): if (arr[i] = = x or arr[i] = = y): # we will check if p is not equal to -1 and # If the element at current index matches with # the element at index p , If yes then update # the minimum distance if needed if (p ! = - 1 and arr[i] ! = arr[p]): min_dist = min (min_dist, i - p) # update the previous index p = i # If distance is equal to int max if (min_dist = = 1e6 ): return - 1 return min_dist |
Javascript
class Solution { minDist(a, n, x, y) { // previous index and min distance var i=0,p=-1, min_dist=Number.MAX_VALUE; for (i=0 ; i<n ; i++) { if (a[i] ==x || a[i] == y) { // we will check if p is not equal to -1 and // If the element at current index matches with // the element at index p , If yes then update // the minimum distance if needed if (p != -1 && a[i] != a[p]) min_dist = Math.min(min_dist,i-p); // update the previous index p=i; } } // If distance is equal to var max if (min_dist==Number.MAX_VALUE) return -1; return min_dist; } } |
Time Complexity: O(N), where N is the size of input array
Auxiliary Space: O(1)
Contact Us