Minimum absolute difference in an array

Overview

In this article we will try to solve on the the problem described in Hacker Rank. The name of the problem is Minimum absolute difference in an array

The absolute difference is the positive difference between two values a and b, is written |a – b| or |b – a| and they are equal. If a = 3 and b = 2, then |3 -2| = |2 – 3| = 1. Given an array of integers, find the minimum absolute difference between any two elements in the array.

Example: arr = {-2, 2, 4}

There are 3 pairs of numbers:  [-2, 2], [-2, 4] and [2, 4]. The absolute differences for these pairs are |-2 – 2| = 4, |-2 – 4| = 6 and |2 – 4| = 2. The minimum absolute difference is 2.

Solution

We can use a nested for loop to solve this problem. We need to iterate through the array and find the difference. If the absolute difference is less that the existing one, we will update the value.

int min = Integer.MAX_VALUE;
for (int i = 0; i < arr.length - 1; i++) {
    for (int j = i + 1; j < arr.length; j++) {
        final int value = Math.abs(arr[i] - arr[j]);
        if (value < min) {
            min = value;
        }
    }
}

The time complexity of this is O(n2) because of the nested for loop. There is a more efficient way to solve this problem. We will first sort the array. Then we will find the absolute difference between the two numbers which are next to each other. Since we need to find the minimum the further the elements in the array the more the difference will be.

int min = Integer.MAX_VALUE;
Arrays.sort(arr);
for (int i = 0; i < arr.length - 1; i++) {
    final int absoluteDifferent = Math.abs(arr[i] - arr[i + 1]);
    if (absoluteDifferent < min) {
        min = absoluteDifferent;
    }
}

Test

Below is a simple JUnit test to check our code above:

MinAbsoluteDiffInArrayTest.java
package com.zia;

import org.junit.Test;

import static org.junit.Assert.*;

public class MinAbsoluteDiffInArrayTest {

    @Test
    public void minimumAbsoluteDifference() {
        assertEquals(2, MinAbsoluteDiffInArray.minimumAbsoluteDifference(new int[]{-2,2,4}));
        assertEquals(3, MinAbsoluteDiffInArray.minimumAbsoluteDifference(new int[]{3,-7,0}));
        assertEquals(1, MinAbsoluteDiffInArray.minimumAbsoluteDifference(new int[]{-59, -36, -13, 1, -53, -92, -2, -96, -54, 75}));
    }
}

Conclusion

In this article we looked at two ways of solving the Minimum absolute difference in an array problem.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: