Minimum Absolute Difference [HackerRank] [Greedy]

Leetcode has a similar problem #1200


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

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

  • int arr[n]: an array of integers

Returns

  • int: the minimum absolute difference found

Input Format

The first line contains a single integer , the size of .
The second line contains  space-separated integers, .

Constraints

  • 2 <= n <= 10 pow 5
  • -10 pow 9 <= arr[i] <= 10 pow 9

Sample Input 0

3
3 -7 0

Sample Output 0

3

Explanation 0

The first line of input is the number of array elements. The array, arr = [3, -7, 0]  There are three pairs to test: (3, -7), (3, 0) , and (-7, 0). The absolute differences are:

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

Remember that the order of values in the subtraction does not influence the result. The smallest of these 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. 

Approach

1. Sort the array in ascending order.

2. Initialize a variable min to track the minimum difference.

3. Iterate through the sorted array:

• For each adjacent pair, compute the difference.


• If the difference is less than the current min, clear the result and update min.


Complexity

• Time complexity:

Sorting: O(n log n)
Scanning: O(n)

Total: O(n log n)

• Space complexity:

O(1) auxiliary 


Solution

Please debug the program here in the godbolt link.

#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);

/*
 * Complete the 'minimumAbsoluteDifference' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts INTEGER_ARRAY arr as parameter.
 */
void printArray(vector<int> arr)
{
   for (auto i : arr) {
       cout << i << " ";
   }
   cout << endl;
}

int minimumAbsoluteDifference(vector<int> arr) {
   sort(arr.begin(), arr.end());
   cout << "After sorting \n";
   printArray(arr);
   auto n = arr.size();
   auto result = INT_MAX;
   for (auto i = 1; i < n; i++) {
    auto diff = arr[i] - arr[i-1];
    cout << "Diff arr[" << i << "] and arr[" 
    << i-1 << "] is " << diff << endl;
    if (result > diff) {
        result = diff;
    }
   }
   return result;
}

int main()
{
    vector<int> arr = {1, -3, 71, 68, 17};
    auto n = arr.size();
    printArray(arr);
    int result = minimumAbsoluteDifference(arr);
    cout << "Minimum Absolute Difference is  " <<  result << "\n\n";
    arr = {3, -7, 0};
    n = arr.size();
    printArray(arr);
    result = minimumAbsoluteDifference(arr);
    cout << "Minimum Absolute Difference is  " <<  result << "\n\n";

    arr = {-59, -36, -13, 1, -53, -92, -2, -96, -54, 75};  
    n = arr.size();
    printArray(arr);
    result = minimumAbsoluteDifference(arr);
    cout << "Minimum Absolute Difference is  " <<  result << "\n\n";
   
    return 0;
}


Output

1 -3 71 68 17 
After sorting 
-3 1 17 68 71 
Diff arr[1] and arr[0] is 4
Diff arr[2] and arr[1] is 16
Diff arr[3] and arr[2] is 51
Diff arr[4] and arr[3] is 3
Minimum Absolute Difference is  3

3 -7 0 
After sorting 
-7 0 3 
Diff arr[1] and arr[0] is 7
Diff arr[2] and arr[1] is 3
Minimum Absolute Difference is  3

-59 -36 -13 1 -53 -92 -2 -96 -54 75 
After sorting 
-96 -92 -59 -54 -53 -36 -13 -2 1 75 
Diff arr[1] and arr[0] is 4
Diff arr[2] and arr[1] is 33
Diff arr[3] and arr[2] is 5
Diff arr[4] and arr[3] is 1
Diff arr[5] and arr[4] is 17
Diff arr[6] and arr[5] is 23
Diff arr[7] and arr[6] is 11
Diff arr[8] and arr[7] is 3
Diff arr[9] and arr[8] is 74
Minimum Absolute Difference is  1

References

  1. Leetcode — https://leetcode.com/problems/minimum-absolute-difference/description/
  2. HackerRank — https://www.hackerrank.com/challenges/minimum-absolute-difference-in-an-array/problem?isFullScreen=true
  3. Godbolt — https://godbolt.org/z/8T4vYjarb
  4. Github — https://github.com/sayhi2shirley/hackerrank-greedy/blob/main/minimum_absolute_difference_in_an_array.cpp
  5. Blogger — https://shirleyanengineer.blogspot.com/2025/05/minimum-absolute-difference-hackerrank.html
  6. Medium - https://medium.com/@developer_notes/minimum-absolute-difference-hackerrank-greedy-126533e31ceb



Comments

Post a Comment