CODEWITHSUNDEEP
algorithm
OneMoreError
OneMoreError

Reputation: 7728

Finding out the minimum difference between elements in an array

I have an integer array with some finite number of values. My job is to find the minimum difference between any two elements in the array.

Consider that the array contains 

4, 9, 1, 32, 13

Here the difference is minimum between 4 and 1 and so answer is 3.

What should be the algorithm to approach this problem. Also, I don't know why but I feel that using trees, this problem can be solved relatively easier. Can that be done?

Upvotes: 31

Views: 97369

Answers (9)

Marco Luzzara
Marco Luzzara

Reputation: 6026

For those of you who are looking for a one-line answer (more or less), these are 2 possible solutions:

Python >= 3.10

l = sorted([4, 9, 1, 32, 13])
min(map(lambda x: x[1] - x[0], pairwise(l)))

From Python 3.10 you can use pairwise() that takes an iterable and returns all consecutive pairs of it. After we sort the initial list, we just need to find the pair with the minimum difference.

Python < 3.10

l = sorted([4, 9, 1, 32, 13])
min(map(lambda x: x[1] - x[0], zip(l[:-1], l[1:])))

In this case, we can reproduce the pairwise() method behavior1 using zip() with 2 slices of the same list so that consecutive elements are paired.

1. The actual implementation of pairwise() is probably more efficient in terms of space because it doesn't need to create 2 (shallow) copies of the list. In most cases, this should not be necessary, but you can use itertools.islice to iterate over the list without creating a copy of it. Then, you would write something like zip(islice(a, len(a) - 1), islice(a, 1, None)).

Upvotes: 1

Pikachu
Pikachu

Reputation: 314

The given problem can easily be solved in O(n) time. Look at the following code that I wrote.

    import java.util.Scanner;
    public class Solution {
    public static void main(String [] args) {
        Scanner input = new Scanner(System.in);
        int i, minDistance = 999999;
        boolean flag = false;
        int capacity = input.nextInt();
        int arr[] = new int[capacity];
        for (i = 0; i < capacity; i++) {
            arr[i] = input.nextInt();
        }

        int firstElement = input.nextInt();
        int secondElement = input.nextInt();

        int prev = 0;

        for (i = 0; i < capacity; i++) {
            if (arr[i] == firstElement || arr[i] == secondElement) {
                prev = i;
                break;
            }
        }

        for (; i < capacity; i++) {
            if(arr[i] == firstElement || arr[i] == secondElement) {
                if(arr[i] != arr[prev] && minDistance > Math.abs(i - prev)) {
                    minDistance = Math.abs(i - prev);
                    flag = true;
                    prev = i;
                } else {
                    prev = i;
                }
            }
        }

        if(flag)
            System.out.println(minDistance);
        else
            System.out.println("-1");
    }
}

Upvotes: 1

Prakash S
Prakash S

Reputation: 652

In Python 3 this problem can be simplified by using the module itertools which gives the combinations available for a list. From that list we can find the sum of each combination and find the minimum of those values. 

import itertools

arr = [4, 9, 1, 32, 13]

if len(arr) > 1:
    min_diff = abs(arr[0] - arr[1])
else:
    min_diff = 0

for n1, n2 in itertools.combinations(arr, 2): # Get the combinations of numbers
    diff = abs(n1-n2) # Find the absolute difference of each combination
    if min_diff > diff:
        min_diff = diff # Replace incase a least differnce found

print(min_diff)

Upvotes: -1

dinesh_malhotra
dinesh_malhotra

Reputation: 1877

sharing the simplest solution.

function FindMin(arr) {

    //sort the array in increasing order

    arr.sort((a,b) => {
       return a-b;
    });

    let min = arr[1]-arr[0];

    let n = arr.length;

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

      let m = arr[i+1] - arr[i];
      if(m < min){
        m = min;
      }
    }

    return m; // minimum difference.
  }

Upvotes: 2

Suhail Gupta
Suhail Gupta

Reputation: 23206

While all the answers are correct, I wanted to show the underlying algorithm responsible for n log n run time. The divide and conquer way of finding the minimum distance between the two points or finding the closest points in a 1-D plane.

The general algorithm:

enter image description here

  • Let m = median(S).
  • Divide S into S1, S2 at m.
  • δ1 = Closest-Pair(S1).
  • δ2 = Closest-Pair(S2).
  • δ12 is minimum distance across the cut.
  • Return δ = min(δ1, δ2, δ12).

Here is a sample I created in Javascript:

// Points in 1-D
var points = [4, 9, 1, 32, 13];

var smallestDiff;

function mergeSort(arr) {
  if (arr.length == 1)
    return arr;

  if (arr.length > 1) {
    let breakpoint = Math.ceil((arr.length / 2));
    // Left list starts with 0, breakpoint-1
    let leftList = arr.slice(0, breakpoint);
    // Right list starts with breakpoint, length-1
    let rightList = arr.slice(breakpoint, arr.length);

    // Make a recursive call
    leftList = mergeSort(leftList);
    rightList = mergeSort(rightList);

    var a = merge(leftList, rightList);
    return a;
  }
}

function merge(leftList, rightList) {
  let result = [];
  while (leftList.length && rightList.length) {
    // Sorting the x coordinates
    if (leftList[0] <= rightList[0]) {
      result.push(leftList.shift());
    } else {
      result.push(rightList.shift());
    }
  }

  while (leftList.length)
    result.push(leftList.shift());

  while (rightList.length)
    result.push(rightList.shift());

  let diff;
  if (result.length > 1) {
    diff = result[1] - result[0];
  } else {
    diff = result[0];
  }

  if (smallestDiff) {
    if (diff < smallestDiff)
      smallestDiff = diff;
  } else {
    smallestDiff = diff;
  }
  return result;
}

mergeSort(points);

console.log(`Smallest difference: ${smallestDiff}`);

Upvotes: 7

Saket Mittal
Saket Mittal

Reputation: 3876

This is actually a restatement of the closest-pair problem in one-dimension. https://en.wikipedia.org/wiki/Closest_pair_of_points_problem http://www.cs.umd.edu/~samir/grant/cp.pdf

As the Wikipedia article cited below points out, the best decision-tree model of this problem also runs in Ω(nlogn) time.

Upvotes: 4

mookid
mookid

Reputation: 1172

You can take advantage of the fact that you are considering integers to make a linear algorithm:

  1. First pass: compute the maximum and the minimum
  2. Second pass: allocate a boolean array of length (max - min + 1), false initialized, and change the (value - min)th value to true for every value in the array
  3. Third pass: compute the differences between the indexes of the true valued entries of the boolean array.

Upvotes: 14

polerto
polerto

Reputation: 1790

I would put them in a heap in O(nlogn) then pop one by one and get the minimum difference between every element that I pop. Finally I would have the minimum difference. However, there might be a better solution.

Upvotes: 5

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726489

The minimum difference will be one of the differences from among the consecutive pairs in sorted order. Sort the array, and go through the pairs of adjacent numbers looking for the smallest difference:

int[] a = new int[] {4, 9, 1, 32, 13};
Arrays.sort(a);
int minDiff = a[1]-a[0];
for (int i = 2 ; i != a.length ; i++) {
    minDiff = Math.min(minDiff, a[i]-a[i-1]);
}
System.out.println(minDiff);

This prints 3.

Upvotes: 51

Related Questions