Minimum Absolute Difference in an Array – Hackerrank solution- Greedy Problem

Minimum Absolute Difference in an Array – Hackerrank solution- Greedy Problem

4 min read

Consider an array of integers, arr =[arr[0], arr[1], … , arr[n-1]] . We define the absolute difference between two elements, a[i] and a[j] (where i != j), to be the absolute value of a[i] – a[j] .

Given an array of integers, find and print the minimum absolute difference between any two elements in the array. For example, given the array arr = [-2,2,4]  we can create 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.

Function Description

Complete the minimumAbsoluteDifference function in the editor below. It should return an integer that represents the minimum absolute difference between any pair of elements.

minimumAbsoluteDifference has the following parameter(s):

  • n: an integer that represents the length of arr
  • arr: an array of integers

Input Format

The first line contains a single integer n, the size of arr.
The second line contains n space-separated integers arr[i].

Constraints

  • 2 <= n <= 100000
  • -1000000000 <= arr[i] <= 1000000000

Output Format

Print the minimum absolute difference between any two elements in the array.

Sample Input 0

3
3 -7 0

Sample Output 0

3

Explanation 0

With n = 3 integers in our array, we have three possible pairs: (3, -7), (3,0), and (-7,0). The absolute values of the differences between these pairs are as follows:

  • | 3 – -7| = 10
  • |3 – 0| = 3
  • |-7 – 0| = 7

Notice that if we were to switch the order of the numbers in these pairs, the resulting absolute values would still be the same. The smallest of these possible absolute differences is 3.

Sample Input 1

10
-59 -36 -13 1 -53 -92 -2 -96 -54 75

Sample Output 1

1

Explanation 1

The smallest absolute difference is |-54 – -53| = 1.

Sample Input 2

5
1 -3 71 68 17

Sample Output 2

3

Explanation 2

The minimum absolute difference is |71 – 68| = 3.

Solution in Python 3

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the minimumAbsoluteDifference function below.
def minimumAbsoluteDifference(arr):
    # Sort array in non-decreasing order 
    arr = sorted(arr) 
  
    # Initialize difference as infinite 
    diff = 10**20
  
    # Find the min diff by comparing adjacent 
    # pairs in sorted array 
    for i in range(n-1): 
        if arr[i+1] - arr[i] < diff: 
            diff = arr[i+1] - arr[i] 
    return diff

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    arr = list(map(int, input().rstrip().split()))
    

    result = minimumAbsoluteDifference(arr)
    
    fptr.write(str(result) + '\n')

    fptr.close()

Solution in Python

Author: shashank21j

n = input()
mini = 10**10
arr = map(int, raw_input().split())
arr.sort()
for i in range(n - 1):
    mini = min(mini, abs(arr[i] - arr[i+1]))
print mini

Solution in Java

Author: AllisonP

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for(int arr_i=0; arr_i < n; arr_i++){
            a[arr_i] = in.nextInt();
        }
        in.close();
        
        Arrays.sort(a);
        int minDiff = a[n - 1] - a[0];
        for (int i = 0; i < n - 1; i++) {
            int tmpDiff = a[i + 1] - a[i];
            if (tmpDiff < minDiff) {
                minDiff = tmpDiff;
            }
        }
        
        System.out.println(minDiff);
    }
}

Solution

Author: StefanK

  1. Sort the array of n numbers using a built-in method in your submission language of choice (you can write a sorting algorithm yourself, but built-in methods are almost always faster).
  2. Create a variable to track the running minimum absolute difference between any two elements and initialize it to some valid possible minimum (e.g., the absolute difference between the highest and lowest possible values for a in the Constraints, the absolute difference between the first and last elements of the sorted array, etc.).
  3. Iterate through the array and calculate the absolute value of the difference between each pair of adjacent elements. You can alleviate the need to take the absolute value of the difference between ai and ai+1 by calculating the difference as ai+1 – ai; this is because sorting ensures that ai is always <= ai+1, so the result of this calculation will always be positive.Check the absolute difference between each adjacent pair of elements against the running minimum absolute difference variable. If the absolute difference between some pair of adjacent elements is less than the value stored in the running minimum variable, set that pair’s absolute difference as the new running minimum.
  4. Print the final value of the running minimum absolute difference variable.
Choose your Reaction!
Leave a Comment