Minimum distance code in python

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

Nội dung chính Show

How do you find the minimum distance in Python?
How do you find the minimum distance between code words?
How do you find the minimum distance in data structure?

Examples:

Input: arr[] = {1, 2}, x = 1, y = 2
Output: Minimum distance between 1 
and 2 is 1.
Explanation: 1 is at index 0 and 2 is at 
index 1, so the distance is 1

Input: arr[] = {3, 4, 5}, x = 3, y = 5
Output: Minimum distance between 3 
and 5 is 2.
Explanation:3 is at index 0 and 5 is at 
index 2, so the distance 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.
Explanation:3 is at index 0 and 6 is at 
index 5, so the distance 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.
Explanation:3 is at index 7 and 2 is at 
index 6, so the distance is 1

Method 1:

Approach: The task is to find the distance between two given numbers, So find the distance between any two elements using nested loops. The outer loop for selecting the first element (x) and the inner loop for traversing the array in search for the other element (y) and taking the minimum distance between them.
Algorithm:
1. Create a variable m = INT_MAX
2. 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).
3. If the ith element is x and jth element is y or vice versa, update m as m = min(m,j-i)
4. Print the value of m as minimum distance
Implementation:

C++

#include <bits/stdc++.h>

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);

}

if (min_dist > n) {

return -1;

}

return min_dist;

}

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;

}

C

#include <limits.h> // for INT_MAX

#include <stdio.h>

#include <stdlib.h> // for abs()

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);

}

if (min_dist > n) {

return -1;

}

return min_dist;

}

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 = 0;

int y = 6;

printf("Minimum distance between %d and %d is %d\n", x,

y, minDist(arr, n, x, y));

return 0;

}

Java

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);

}

if (min_dist > n) {

return -1;

}

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 = 0;

int y = 6;

System.out.println("Minimum distance between " + x

+ " and " + y + " is "

+ min.minDist(arr, n, x, y));

}

Python3

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

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))

C#

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;

}

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));

}

PHP

<?php

function minDist($arr, $n, $x, $y)

{

$i; $j;

$min_dist = PHP_INT_MAX;

for ($i = 0; $i < $n; $i++)

{

for ($j = $i + 1; $j < $n; $j++)

{

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);

}

if($min_dist>$n)

{

return -1;

}

return $min_dist;

}

$arr = array(3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3);

$n = count($arr);

$x = 0;

$y = 6;

echo "Minimum distance between ",$x, " and ",$y," is ";

echo minDist($arr, $n, $x, $y);

?>

Javascript

<script>

function minDist(arr, n, x, y)

{

var i, j;

var min_dist = Number.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);

}

if(min_dist>n)

{

return -1;

}

return min_dist;

}

var arr = [ 3, 5, 4, 2, 6, 5,

6, 6, 5, 4, 8, 3 ];

var n = arr.length;

var x = 3;

var y = 6;

document.write("Minimum distance between " + x +

" and " + y + " is " +

minDist(arr, n, x, y));

</script>

Output

Minimum distance between 3 and 6 is 4

Complexity Analysis:
- Time Complexity: O(n^2), Nested loop is used to traverse the array.
- Space Complexity: O(1), no extra space is required.

Method 2:

Approach: So 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 a y, then how to get the minimum distance between pairs. By analyzing closely it can be seen that every x followed by a y or vice versa can only be the closest pair (minimum distance) so ignore all other pairs.
Algorithm:
1. Create a variable prev=-1 and m= INT_MAX
2. Traverse through the array from start to end.
3. If the current element is x or y, prev is not equal to -1 and array[prev] is not equal to current element then update m = max(current_index – prev, m), i.e. find the distance between consecutive pairs and update m with it.
4. print the value of m
Thanks to wgpshashank for suggesting this approach.

Implementation.

C++

#include <bits/stdc++.h>

using namespace std;

int minDist(int arr[], int n, int x, int y)

{

int p = -1, min_dist = INT_MAX;

for(int i=0 ; i<n ; i++)

{

if(arr[i]==x || arr[i]==y)

{

if( p != -1 && arr[i] != arr[p])

min_dist = min(min_dist , i-p);

p=i;

}

if(min_dist==INT_MAX)

return -1;

return min_dist;

}

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;

}

C

#include <stdio.h>

#include <limits.h> // For INT_MAX

int min(int a ,int b)

{

if(a < b)

return a;

return b;

}

int minDist(int arr[], int n, int x, int y)

{

int i=0,p=-1, min_dist=INT_MAX;

for(i=0 ; i<n ; i++)

{

if(arr[i] ==x || arr[i] == y)

{

if(p != -1 && arr[i] != arr[p])

min_dist = min(min_dist,i-p);

p=i;

}

if(min_dist==INT_MAX)

return -1;

return min_dist;

}

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\n", 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,p=-1, min_dist=Integer.MAX_VALUE;

for(i=0 ; i<n ; i++)

{

if(arr[i] ==x || arr[i] == y)

{

if(p != -1 && arr[i] != arr[p])

min_dist = Math.min(min_dist,i-p);

p=i;

}

if(min_dist==Integer.MAX_VALUE)

return -1;

return min_dist;

}

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):

i=0

p=-1

min_dist = sys.maxsize;

for i in range(n):

if(arr[i] ==x or arr[i] == y):

if(p != -1 and arr[i] != arr[p]):

min_dist = min(min_dist,i-p)

p=i

if(min_dist == sys.maxsize):

return -1

return min_dist

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\n"%( x, y,minDist(arr, n, x, y)));

C#

using System;

class MinimumDistance {

static int minDist(int []arr, int n,

int x, int y)

{

int i=0,p=-1, min_dist=int.MaxValue;

for(i=0 ; i<n ; i++)

{

if(arr[i] ==x || arr[i] == y)

{

if(p != -1 && arr[i] != arr[p])

min_dist = Math.Min(min_dist,i-p);

p=i;

}

if(min_dist==int.MaxValue)

return -1;

return min_dist;

}

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));

}

PHP

<?php

function minDist($arr, $n, $x, $y)

{

$i=0;

$p=-1;

$min_dist=PHP_INT_MAX;

for($i=0 ; $i<$n ; $i++)

{

if($arr[$i] ==$x || $arr[$i] == $y)

{

if($p != -1 && $arr[$i] != $arr[$p])

$min_dist = min($min_dist,$i-$p);

$p=$i;

}

if($min_dist==PHP_INT_MAX)

return -1;

return $min_dist;

}

$arr =array(3, 5, 4, 2, 6, 3, 0, 0, 5,

4, 8, 3);

$n = count($arr);

$x = 3;

$y = 6;

echo "Minimum distance between $x and ",

"$y is ", minDist($arr, $n, $x, $y);

?>

Javascript

<script>

function minDist(arr , n , x , y)

{

var i=0,p=-1, min_dist=Number.MAX_VALUE;

for(i=0 ; i<n ; i++)

{

if(arr[i] ==x || arr[i] == y)

{

if(p != -1 && arr[i] != arr[p])

min_dist = Math.min(min_dist,i-p);

p=i;

}

if(min_dist==Number.MAX_VALUE)

return -1;

return min_dist;

}

var arr = [3, 5, 4, 2, 6, 3, 0, 0, 5, 4, 8, 3];

var n = arr.length;

var x = 3;

var y = 6;

document.write("Minimum distance between " + x + " and " + y

+ " is " + minDist(arr, n, x, y));

</script>

Output

Minimum distance between 3 and 6 is 1

Complexity Analysis:
Time Complexity: O(n).
Only one traversal of the array is needed.
Space Complexity: O(1).
As no extra space is required.

Method 3:

Approach: The problem says that we want a minimum distance between x and y. So the approach is traverse the array and while traversing in array if we got the number as x or y then we will store the difference between indices of previously found x or y and newly find x or y and like this for every time we will try to minimize the difference.
Algorithm:

Create variables idx1 = -1, idx2 = -1 and min_dist = INT_MAX;
Traverse the array from i = 0 to i = n-1 where n is the size of array.
While traversing if the current element is x then store index of current element in idx1 or if the current element is y then store index of current element in idx2.
If idx1 and idx2 variable are not equal to -1 then store minimum of min_dist, difference of idx1 and idx2 into ans.
At the end of traversal, if idx1 or idx2 are still -1(x or y not found in array) then return -1 or else return min_dist.

Implementation:

C++

#include <bits/stdc++.h>

using namespace std;

int minDist(int arr[], int n, int x, int y)

{

int idx1=-1,idx2=-1,min_dist = INT_MAX;

for(int i=0;i<n;i++)

{

if(arr[i]==x)

{

idx1=i;

}

else if(arr[i]==y)

{

idx2=i;

}

if(idx1!=-1 && idx2!=-1)

min_dist=min(min_dist,abs(idx1-idx2));

}

if(idx1==-1||idx2==-1)

return -1;

else

return min_dist;

}

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;

}

Java

public class GFG {

static int minDist(int arr[], int n, int x, int y)

{

int idx1 = -1, idx2 = -1,

min_dist = Integer.MAX_VALUE;

for (int i = 0; i < n; i++) {

if (arr[i] == x) {

idx1 = i;

}

else if (arr[i] == y) {

idx2 = i;

}

if (idx1 != -1 && idx2 != -1)

min_dist = Math.min(min_dist,

Math.abs(idx1 - idx2));

}

if (idx1 == -1 || idx2 == -1)

return -1;

else

return min_dist;

}

public static void main(String[] args)

{

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 "

+ minDist(arr, n, x, y));

}

Python3

import sys

def minDist(arr, n, x, y) :

idx1=-1; idx2=-1; min_dist = sys.maxsize;

for i in range(n) :

if arr[i]==x :

idx1=i

elif arr[i]==y :

idx2=i

if idx1!=-1 and idx2!=-1 :

min_dist=min(min_dist,abs(idx1-idx2));

if idx1==-1 or idx2==-1 :

return -1

else :

return min_dist

if __name__ == "__main__" :

arr = [ 3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3]

n = len(arr)

x = 3

y = 6

print ("Minimum distance between %d and %d is %d\n"%( x, y,minDist(arr, n, x, y)));

C#

using System;

class MinimumDistance {

static int minDist(int []arr, int n,

int x, int y)

{

int idx1=-1,idx2=-1,min_dist = int.MaxValue;

for(int i=0;i<n;i++)

{

if(arr[i]==x)

{

idx1=i;

}

else if(arr[i]==y)

{

idx2=i;

}

if(idx1!=-1 && idx2!=-1)

min_dist=Math.Min(min_dist,Math.Abs(idx1-idx2));

}

if(idx1==-1||idx2==-1)

return -1;

else

return min_dist;

}

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));

}

Javascript

<script>

function minDist(arr , n , x , y)

{

var idx1=-1,idx2=-1,min_dist = Number.MAX_VALUE;

for(var i=0;i<n;i++)

{

if(arr[i]==x)

{

idx1=i;

}

else if(arr[i]==y)

{

idx2=i;

}

if(idx1!=-1 && idx2!=-1)

min_dist=Math.min(min_dist,Math.abs(idx1-idx2));

}

if(idx1==-1||idx2==-1)

return -1;

else

return min_dist;

}

var arr = [ 3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3];

var n = arr.length;

var x = 3;

var y = 6;

document.write("Minimum distance between " + x + " and " + y

+ " is " + minDist(arr, n, x, y));

</script>

Output

Minimum distance between 3 and 6 is 4

Complexity Analysis:
Time Complexity: O(n).
Only one traversal of the array is required.
Space Complexity: O(1).
No extra space is required.

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

How do you find the minimum distance in Python?

To solve this, we will follow these steps:.

minimum := infinity..

for i in range 0 to size of nums, do. if nums[i] is same as target, then. if |i - start| < minimum, then. minimum := |i - start|.

return minimum..

How do you find the minimum distance between code words?

A code's minimum distance is the minimum of d(u,v) over all distinct codewords u and v. If the minimum distance is at least 2t + 1, a nearest neighbor decoder will always decode correctly when there are t or fewer errors.