CODEWITHSUNDEEP
javascriptarrays
aakriti1711
aakriti1711

Reputation: 44

Minumum distance between two numers in Array using Javascript

I am looking for a better solution for getting minimum distance between 2 elements in an array. 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.

I have this Code in JS & it works fine for now. I am looking for better code for achieving the same. Thanks!!

<script>
var numbers= ["2", "3", "5","7","1","2","3","4","8"];
var x ="5";
var y ="8";
var firstIndex = numbers.indexOf(x);

var minD = numbers.length;

var x= numbers.forEach(function(item,index){

if((item == x) || (item == y))
{
    if((index != firstIndex) && (index-firstIndex < minD))
    {
    minD = index-firstIndex;
    firstIndex = index;
    }
    else
    {
    firstIndex = index;
    }
 }

});
alert(minD);

document.getElementById("demo").innerHTML = minD;
</script>

Upvotes: 1

Views: 2665

Answers (4)

vsync
vsync

Reputation: 130401

Assuming the array can be extremely large, I would rather not sort it before iterating, as it is not an efficient strategy.

The below logic scans the array from left-to-right, so in each iteration, the number marked with 👉 is checked against all proceeding numbers, until the best match is found, and then the same happens width the next number, until all possibilities have been calculated and the best (lowest) outcome is saved (minDis).

 👉  -  -   -   -   -  🔥
[50, 5, 75, 66, 32, 4, 58] // diff between 50 and each number past it (min is 8)

     👉 -   -   -  🔥  -
[50, 5, 75, 66, 32, 4, 58] // diff between 5 and each number past it (min is 1)

        👉  🔥  -   -   -
[50, 5, 75, 66, 32, 4, 58] // diff between 75 and each number past it (min is 9)
...

On each iteration in the recursion the minDis parameter is sent to the deeper level so the local diff of that level (the for loop) is compared against that minDis argument, and if there's a smaller diff, it is then set as the "new" minDis value:

var data = [50, 5, 75, 66, 32, 4, 58]; // assume a very large array

// find the minimum distance between two numbers
function findMinDistance(arr, minDis = Infinity, idx = 0){ 
  for( var numIdx = idx; numIdx < arr.length; numIdx++ ){
    var diff = Math.abs(arr[idx] - arr[numIdx+1])
    if( diff < minDis ) minDis = diff
    // no need to continue scanning, since "0" is the minimum possible
    if( minDis === 0 ) return 0
  }
  
  // scan from left to right, so each item is compared to the ones past it
  return idx < arr.length - 1 && minDis > 0 
    ? findMinDistance(arr, minDis, idx+1) 
    : minDis
}

console.log(`Min distance is: ${findMinDistance(data)}`)

A non-recursive approach, similar to the above:

var data = [50, 5, 75, 66, 32, 4, 58]; // assume a very large array

// find the minimum distance between two numbers
function findMinDistance(arr){
  var minDis = Infinity, idx = 0, numIdx = idx
  
  for( ; numIdx < arr.length; numIdx++ ){
    var diff = Math.abs(arr[idx] - arr[numIdx+1])
    
    // if result is lower than minDis, save new minDis
    if( diff < minDis ) 
      minDis = diff 
    
    // "0" is the minimum so no need to continue
    if( minDis === 0 ) 
      return 0 
    
    // go to the next number and compare it to all from its right
    else if( numIdx == arr.length - 1 ) 
      numIdx = ++idx
  }

  return minDis
}

console.log(`min distance is: ${findMinDistance(data)}`)

Upvotes: 0

Suraj Patil
Suraj Patil

Reputation: 180

 
function findMin(arr,a,b){
	var firstIndex = arr.indexOf(a);
  console.log(firstIndex);
  
  var lastIndex = arr.indexOf(b);
  console.log(lastIndex);
  
  var minDistance;
  
  if(firstIndex===lastIndex){
  		minDistance = 1;
  }
  if(firstIndex<lastIndex){
  		minDistance = lastIndex-firstIndex;
  }
	return minDistance;
}

 console.log(findMin([1,2,3,4,5,6],1,5));

Upvotes: 0

Nina Scholz
Nina Scholz

Reputation: 386680

You could keep the indices and optimise the minimum value by testing if the actual difference is smaller.

function getMinDistance(array, left, right) {
    var rightIndex, leftIndex, minDistance;
    array.forEach(function (a, i) {
        if (a === left && (leftIndex === undefined || leftIndex < i)) {
            leftIndex = i;
        }
        if (a === right && leftIndex !== undefined) {
            rightIndex = i;
        }
        if (leftIndex < rightIndex && (minDistance === undefined || minDistance > rightIndex - leftIndex)) {
            minDistance = rightIndex - leftIndex;
        }
    });
    return minDistance
}

console.log(getMinDistance(["2", "3", "5", "7", "1", "2", "3", "4", "8"], "5", "8"));
console.log(getMinDistance([3, 5, 4, 2, 6, 5, 6, 6, 5, 4, 8, 3], 3,  6));

Upvotes: 1

Jonas Wilms
Jonas Wilms

Reputation: 138427

var xs=array.reduce((arr,el,i)=>(!(el===x)||arr.push(i),arr),[]);
var ys=array.reduce((arr,el,i)=>(!(el===y)||arr.push(i),arr),[]);
var lowest= xs.map(ix=>ys.map(iy=>Math.abs(iy-ix)).sort()[0]).sort()[0];

Im not sure if this is really shorter or better, just another approach...

Ive simply filtered out all x and y positions, then calculated the distance between each of them ( iy-ix) and took the smalles value (.sort()[0])

http://jsbin.com/nolohezape/edit?console

Upvotes: 1

Related Questions