Minimum Distance Between Two Numbers

Easy

0/40

Average time to solve is 15m

Contributed by

15 upvotes

Asked in company

Problem statement

You’re given an array of 'N' integers, and two integers 'X' and 'Y'. Your task is to find the minimum distance between 'X' and 'Y' in the array. If either or both of them are not present in the array then return -1.

NOTE :

1. The array might also contain duplicates. 
2. It is guaranteed that 'X' and 'Y' are two distinct integers i.e. 'X' is not equal to 'Y'.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains an integer 'T', denoting the number of test cases.

The first line of each test case contains three space-separated integers 'N', 'X', 'Y', as described in the problem statement.

The second line of each test case contains 'N' space-separated integers, the elements of the array.

Output Format :

For each test case, print the minimum distance between 'X' and 'Y' and if any or both of them('X' and 'Y') are not present in the array then print -1.

Print the output of each test case in a separate line

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= N <= 10^5
0 <= X, Y <= 10^9
0 <= ARR[i] <= 10^9

Where 'T' denotes the number of test cases, 'N' denotes the number of elements in the array ‘ARR’ respectively, 'X' and 'Y' denotes the integer given in the input, and 'ARR[i]' denotes the 'i-th' element of the array 'ARR'. 

Time Limit : 1 sec

Sample Input 1 :

1
3 3 5
3 4 5

Sample Output 1 :

Explanation of Sample Input 1 :

As 3 is at the first position and 5 is at third position. Hence, the minimum distance between 3 and 5 is 2.

Sample Input 2 :

Sample Output 2 :

1
-1

Explanation of Sample Input 2 :

There are two distances between 1 and 2, which are 1 and 3. Out of these two, 1 is the minimum distance.
We return -1 as X = 2 and Y = 3 doesn’t exist in our array.

Hint 1

Hint 2

Brute Force

Approaches (2)

Approach 1

Approach 2

Brute Force Approach

Approach: In this approach, we’ll use brute force. As we are supposed to find the minimum distance between the two integers, we’ll do this by using nested loops. The outer loop will be used for selecting the X(our first element) and the inner loop will be used for traversing the array in search for Y(another element) and taking the minimum distance between them. Let us understand how we will implement these steps.

First, we’ll start by creating a variable minimunDist = INT_MAX
Then we will run a nested loop, the outer loop runs from start to end (loop counter i), the inner loop runs from i+1 to end (loop counter j).
If the ith element is X and the jth element is Y or vice versa, we will update m as minimunDist = min(minimunDist,j-i)
Print the value of minimunDist as minimum distance.

Time Complexity

O(N^2), where N is the size of the array.

As we are using nested loops, we’ll require N^2 operations, hence time complexity will be O(N^2).

Space Complexity

O(1).

We are using constant extra memory. Hence, the overall space complexity is O(1).

(100% EXP penalty)

Minimum Distance Between Two Numbers

Console