# Find the minimum distance between two numbers

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[].

Examples:
Input: arr[] = {1, 2}, x = 1, y = 2
Output: Minimum distance between 1 and 2 is 1.

Input: arr[] = {3, 4, 5}, x = 3, y = 5
Output: Minimum distance between 3 and 5 is 2.

Input: arr[] = {3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3}, x = 3, y = 6
Output: Minimum distance between 3 and 6 is 4.

Input: arr[] = {2, 5, 3, 5, 4, 4, 2, 3}, x = 3, y = 2
Output: Minimum distance between 3 and 2 is 1.

Method 1 (Simple)
Use two loops: The outer loop picks all the elements of arr[] one by one. The inner loop picks all the elements after the element picked by outer loop. If the elements picked by outer and inner loops have same values as x or y then if needed update the minimum distance calculated so far.

## C++

 `// C++ program to Find the minimum ` `// distance between two numbers ` `#include ` `using` `namespace` `std;  ` ` `  `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; ` `} ` ` `  `/* Driver code */` `int` `main()  ` `{ ` `    ``int` `arr[] = {3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]); ` `    ``int` `x = 3; ` `    ``int` `y = 6; ` ` `  `    ``cout << ``"Minimum distance between "` `<< x <<  ` `                    ``" and "` `<< y << ``" is "` `<<  ` `                    ``minDist(arr, n, x, y) << endl; ` `} ` ` `  `// This code is contributed by Shivi_Aggarwal `

## C

 `// C program to Find the minimum ` `// distance between two numbers ` `#include ` `#include // for abs() ` `#include // for INT_MAX ` ` `  `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; ` `} ` ` `  `/* Driver program to test above fnction */` `int` `main()  ` `{ ` `    ``int` `arr[] = {3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]); ` `    ``int` `x = 3; ` `    ``int` `y = 6; ` ` `  `    ``printf``(````"Minimum distance between %d and %d is %d "````, x, y,  ` `              ``minDist(arr, n, x, y)); ` `    ``return` `0; ` `} `

## Java

 `// Java Program to Find the minimum ` `// distance between two numbers ` `class` `MinimumDistance  ` `{ ` `    ``int` `minDist(``int` `arr[], ``int` `n, ``int` `x, ``int` `y)  ` `    ``{ ` `        ``int` `i, j; ` `        ``int` `min_dist = Integer.MAX_VALUE; ` `        ``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 > Math.abs(i - j))  ` `                    ``min_dist = Math.abs(i - j); ` `            ``} ` `        ``} ` `        ``return` `min_dist; ` `    ``} ` ` `  `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` `        ``MinimumDistance min = ``new` `MinimumDistance(); ` `        ``int` `arr[] = {``3``, ``5``, ``4``, ``2``, ``6``, ``5``, ``6``, ``6``, ``5``, ``4``, ``8``, ``3``}; ` `        ``int` `n = arr.length; ` `        ``int` `x = ``3``; ` `        ``int` `y = ``6``; ` ` `  `        ``System.out.println(``"Minimum distance between "` `+ x + ``" and "` `+ y  ` `                ``+ ``" is "` `+ min.minDist(arr, n, x, y)); ` `    ``} ` `} `

## Python3

 `# Python3 code to Find the minimum ` `# distance between two numbers ` ` `  `def` `minDist(arr, n, x, y): ` `    ``min_dist ``=` `99999999` `    ``for` `i ``in` `range``(n): ` `        ``for` `j ``in` `range``(i ``+` `1``, n): ` `            ``if` `(x ``=``=` `arr[i] ``and` `y ``=``=` `arr[j] ``or` `            ``y ``=``=` `arr[i] ``and` `x ``=``=` `arr[j]) ``and` `min_dist > ``abs``(i``-``j): ` `                ``min_dist ``=` `abs``(i``-``j) ` `        ``return` `min_dist ` ` `  ` `  `# Driver code ` `arr ``=` `[``3``, ``5``, ``4``, ``2``, ``6``, ``5``, ``6``, ``6``, ``5``, ``4``, ``8``, ``3``] ` `n ``=` `len``(arr) ` `x ``=` `3` `y ``=` `6` `print``(``"Minimum distance between "``,x,``" and "``, ` `     ``y,``"is"``,minDist(arr, n, x, y)) ` ` `  `# This code is contributed by "Abhishek Sharma 44" `

## C#

 `// C# code to Find the minimum ` `// distance between two numbers ` `using` `System; ` ` `  `class` `GFG { ` `     `  `    ``static` `int` `minDist(``int` `[]arr, ``int` `n, ` `                           ``int` `x, ``int` `y)  ` `    ``{ ` `        ``int` `i, j; ` `        ``int` `min_dist = ``int``.MaxValue; ` `        ``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 > ` `                   ``Math.Abs(i - j)) ` `                    `  `                    ``min_dist = ` `                    ``Math.Abs(i - j); ` `            ``} ` `        ``} ` `        ``return` `min_dist; ` `    ``} ` `     `  `    ``// Driver function ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int` `[]arr = {3, 5, 4, 2, 6, ` `              ``5, 6, 6, 5, 4, 8, 3}; ` `        ``int` `n = arr.Length; ` `        ``int` `x = 3; ` `        ``int` `y = 6; ` ` `  `        ``Console.WriteLine(``"Minimum "` `               ``+ ``"distance between "` `         ``+ x +  ``" and "` `+ y + ``" is "`  `           ``+ minDist(arr, n, x, y)); ` `    ``} ` `} ` ` `  `// This code is contributed by Sam007 `

## PHP

 ` ``abs``(``\$i` `- ``\$j``)) ` `            ``{ ` `                ``\$min_dist` `= ``abs``(``\$i` `- ``\$j``); ` `            ``} ` `        ``} ` `    ``} ` `    ``return` `\$min_dist``; ` `} ` ` `  `    ``// Driver Code ` `    ``\$arr` `= ``array``(3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3); ` `    ``\$n` `= ``count``(``\$arr``); ` `    ``\$x` `= 3; ` `    ``\$y` `= 6; ` ` `  `    ``echo` `"Minimum distance between "``,``\$x``, ``" and "``,``\$y``,``" is "``;  ` `    ``echo` `minDist(``\$arr``, ``\$n``, ``\$x``, ``\$y``); ` ` `  `// This code is contributed by anuj_67. ` `?> `

Output:

`Minimum distance between 3 and 6 is 4`

Time Complexity: O(n^2)

Method 2 (Tricky)
1) Traverse array from left side and stop if either x or y is found. Store index of this first occurrence 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.

Thanks to wgpshashank for suggesting this approach.

## C++

 `// C++ implementation of above approach ` `#include ` `using` `namespace` `std; ` ` `  `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; ` `} ` ` `  `/* Driver code */` `int` `main() ` `{ ` `    ``int` `arr[] = {3, 5, 4, 2, 6, 3, 0, 0, 5, 4, 8, 3}; ` `    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr[0]); ` `    ``int` `x = 3; ` `    ``int` `y = 6; ` ` `  `    ``cout << ``"Minimum distance between "` `<< x << ` `                        ``" and "` `<< y << ``" is "``<< ` `                        ``minDist(arr, n, x, y) << endl; ` `    ``return` `0; ` `} ` ` `  `// This code is contributed by Mukul singh. `

## C

 `#include ` `#include   // For INT_MAX ` ` `  `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; ` `} ` ` `  `/* Driver program to test above fnction */` `int` `main() ` `{ ` `    ``int` `arr[] ={3, 5, 4, 2, 6, 3, 0, 0, 5, 4, 8, 3}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]); ` `    ``int` `x = 3; ` `    ``int` `y = 6; ` ` `  `    ``printf``(````"Minimum distance between %d and %d is %d "````, x, y, ` `              ``minDist(arr, n, x, y)); ` `    ``return` `0; ` `} `

## Java

 `class` `MinimumDistance ` `{ ` `    ``int` `minDist(``int` `arr[], ``int` `n, ``int` `x, ``int` `y)  ` `    ``{ ` `        ``int` `i = ``0``; ` `        ``int` `min_dist = Integer.MAX_VALUE; ` `        ``int` `prev=``0``; ` ` `  `        ``// 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 minimum distance  ` `                ``// so far ` `                ``if` `(arr[prev] != arr[i] && (i - prev) < min_dist)  ` `                ``{ ` `                    ``min_dist = i - prev; ` `                    ``prev = i; ` `                ``}  ` `                ``else` `                    ``prev = i; ` `            ``} ` `        ``} ` ` `  `        ``return` `min_dist; ` `    ``} ` ` `  `    ``/* Driver program to test above functions */` `    ``public` `static` `void` `main(String[] args) { ` `        ``MinimumDistance min = ``new` `MinimumDistance(); ` `        ``int` `arr[] = {``3``, ``5``, ``4``, ``2``, ``6``, ``3``, ``0``, ``0``, ``5``, ``4``, ``8``, ``3``}; ` `        ``int` `n = arr.length; ` `        ``int` `x = ``3``; ` `        ``int` `y = ``6``; ` ` `  `        ``System.out.println(``"Minimum distance between "` `+ x + ``" and "` `+ y ` `                ``+ ``" is "` `+ min.minDist(arr, n, x, y)); ` `    ``} ` `} `

## Python3

 `import` `sys ` ` `  `def` `minDist(arr, n, x, y): ` `    ``min_dist ``=` `sys.maxsize ` ` `  `    ``#Find the first occurence of any of the two numbers (x or y) ` `    ``# and store the index of this occurence in prev ` `    ``for` `i ``in` `range``(n): ` `         `  `        ``if` `arr[i] ``=``=` `x ``or` `arr[i] ``=``=` `y: ` `            ``prev ``=` `i ` `            ``break` `  `  `    ``# Traverse after the first occurence ` `    ``while` `i < n: ` `        ``if` `arr[i] ``=``=` `x ``or` `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] ``and` `(i ``-` `prev) < min_dist : ` `                ``min_dist ``=` `i ``-` `prev ` `                ``prev ``=` `i ` `            ``else``: ` `                ``prev ``=` `i ` `        ``i ``+``=` `1`         `  `  `    ``return` `min_dist ` `  `  `# Driver program to test above fnction */ ` `arr ``=` `[``3``, ``5``, ``4``, ``2``, ``6``, ``3``, ``0``, ``0``, ``5``, ``4``, ``8``, ``3``] ` `n ``=` `len``(arr) ` `x ``=` `3` `y ``=` `6` `print` `(````"Minimum distance between %d and %d is %d "````%``( x, y,minDist(arr, n, x, y))); ` ` `  `# This code is contributed by Shreyanshi Arun. `

## C#

 `// C# program to Find the minimum  ` `// distance between two numbers ` `using` `System; ` `class` `MinimumDistance { ` `     `  `    ``static` `int` `minDist(``int` `[]arr, ``int` `n, ` `                       ``int` `x, ``int` `y)  ` `    ``{ ` `        ``int` `i = 0; ` `        ``int` `min_dist = ``int``.MaxValue; ` `        ``int` `prev=0; ` ` `  `        ``// 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 minimum distance  ` `                ``// so far ` `                ``if` `(arr[prev] != arr[i] &&  ` `                    ``(i - prev) < min_dist)  ` `                ``{ ` `                    ``min_dist = i - prev; ` `                    ``prev = i; ` `                ``}  ` `                ``else` `                    ``prev = i; ` `            ``} ` `        ``} ` ` `  `        ``return` `min_dist; ` `    ``} ` ` `  `    ``// Driver Code ` `    ``public` `static` `void` `Main()  ` `    ``{ ` `         `  `        ``int` `[]arr = {3, 5, 4, 2, 6, 3,  ` `                     ``0, 0, 5, 4, 8, 3}; ` `        ``int` `n = arr.Length; ` `        ``int` `x = 3; ` `        ``int` `y = 6; ` `        ``Console.WriteLine(``"Minimum distance between "` `+ x + ``" and "` `+ y ` `                                       ``+ ``" is "` `+ minDist(arr, n, x, y)); ` `    ``} ` `} ` ` `  `// This code is contributed by anuj_67. `

## PHP

 ` `

Output:

`Minimum distance between 3 and 6 is 1`

Time Complexity: O(n)

Please write comments if you find the above codes/algorithms incorrect, or find other ways to solve the same problem.

## tags:

Arrays Paytm Paytm Arrays