# Minimum Absolute Difference in an Array

# Minimum Absolute Difference in an Array

anjalipv + 26 comments 1)sort 2)consider diff between the first pair as min 3)compare all "consecutive pair min" with the one in step2 to get the least min.

LeHarkunwar + 3 comments Yeah, it was pretty easy after reading your comment.

n,a = input(),sorted(map(int, input().split())) print(min(abs(x-y) for x,y in zip(a,a[1:])))

antdro + 3 comments Check for duplicates helps to avoid unnecessary computations.

if len(arr) != len(list(set(arr))): result = 0

This is relevant for one of the tests.

Sourov_Roy + 1 comment [deleted]ion01 + 0 comments [deleted]

it_henrik + 0 comments to avoid even more unnecessary computations:

`len(list(set(arr))) -> len(set(arr))`

machinekoder + 0 comments You can also abort when diff is zero to pass the test.

wangjiehui11235 + 0 comments it's really nice!

satyavinay456 + 1 comment you are not considering all pairs, zip is not useful in this case

danc1005 + 1 comment Exactly, this just compares 'neighbors' i.e. numbers at consecutive indices (i, i+1)...that's a set of O(n) whereas the set of all possible pairs (given by, for example, set([i, i for i in range(n)]).symmetric_difference(itertools.product(a, a)) is O(n^2)

namik + 0 comments Note that the array was sorted beforehand, so that considering differences of consecutive elements is all we need to check to find the minimum difference. No point in checking the difference between i and i+2 if we know the difference between i and i+1 is definitely less.

joaonoch + 3 comments Here is your approach in C++:

#include <numeric> #include <iterator> using namespace std; typedef long long ll; int main() { ll iNum; cin >> iNum; vector<ll> iVec, sortVec; copy_n(istream_iterator<ll>(cin), iNum, back_inserter(iVec)); sort(begin(iVec),end(iVec)); adjacent_difference(begin(iVec),end(iVec), back_inserter(sortVec)); cout << *min_element(begin(sortVec)+1,end(sortVec)); return 0; }

NiceBuddy + 0 comments without sorting: using multiset;

#include <cmath> #include <limits> #include <set> #include <iostream> #include <algorithm> #include <iterator> using namespace std; #define ll long long int int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, ans=numeric_limits<ll>::max(); cin>>n; multiset<ll> mySet; for(auto i=0; i<n;++i) { ll temp=0; cin>>temp; mySet.insert(temp); } for(auto itr=mySet.begin(); itr!=mySet.end(); ++itr) if(itr!=mySet.begin()) { ll a=*(itr--); ll b=*(itr++); ans=min(ans, abs(a-b)); } cout<<ans<<endl; return 0; }

vshnu8007 + 0 comments [deleted]h170020035 + 3 comments fuke

c170020010 + 0 comments [deleted]reenachowdhary + 0 comments [deleted]ion01 + 0 comments What does that word mean?

kangsman + 0 comments [deleted]sanjay311999 + 2 comments Why should we consider only consecutive pairs? It can be any two elements from the array right?

niketannath + 0 comments As the array has been sorted, so we need to consider the difference between only the consecutive elements. In a sorted array, the difference will increase if you skip elements to calculate the difference.

andrewramka + 0 comments The values that are closest to one another are the ones that will have the least difference.

After sorting I know that for any value, i , the values at i-1 and i+1 are closest to i.Therefore, I dont have to consider all pairs that contain, i, I can just consider the ones that are going to yield the least difference, i's neighbors. Everyone else is farther away.

NandiChaurasiya + 1 comment //Same approch in C++ using vector int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */

int n; cin>>n; vector vec(n); generate(vec.begin(), vec.end(), []{int x; cin>>x; return x;}); sort(vec.begin(), vec.end());`int diff = abs(vec[0] - vec[1]); int sub; for(int i=0; i<(n-1); i++){ sub = abs(vec[i] - vec[i+1]); if(sub < diff) diff = sub; } cout<<diff; return 0;`

}

cougargriff + 3 comments this will only work for checking consecutive elements diff not ANY

ksanner + 0 comments [deleted]NandiChaurasiya + 0 comments forr that we are doing sort(vec.begin(), vec.end());

billchenxi + 0 comments The consecutive elements give the minimal than "any"

phoemur + 1 comment C++ STL

int minimumAbsoluteDifference(vector<int> arr) { sort(begin(arr), end(arr)); adjacent_difference(begin(arr), end(arr), begin(arr), [](int a, int b){ return abs(a-b); }); return *min_element(begin(arr)+1, end(arr)); }

billchenxi + 0 comments Can you explain the part? I understand what it calculating, where did you collect them?

adjacent_difference(begin(arr), end(arr), begin(arr), [](int a, int b){ return abs(a-b); });

afromogli + 1 comment Why do you sort it? In what way does it help?

NandiChaurasiya + 2 comments After sorting, any two consecutive numbers will be having minimum difference for both negative and positive numbers.

harshkirat2 + 1 comment with your approach i am able to pass only 2 test cases, but with my code i am unable to pass only 4th test case,Suggest some changes or another approach. Here is my code in C:

#include<stdio.h> #include<stdlib.h> main() { long int i,j,n; scanf("%ld",&n); long long int min,a[n]; scanf("%lld%lld",&a[0],&a[1]); min=abs(a[0]-a[1]); for(i=2;i<n;i++) { scanf("%lld",&a[i]); for(j=0;j<i;j++) { if(abs(a[j]-a[i])<min) min=abs(a[j]-a[i]); if(min==0) { break; } } if(min==0) break; } printf("%lld",min); }

ksanner + 0 comments Your approach is likely taking too long, since you're running O(n^2)

If you're using just the C stdlib, try using qsort on the data set and then comparing just the neighbors for each element.

matthedm + 0 comments Yup. Of course then we get an Theta nlogn. However this may be the best we can do for this problem

h170020035 + 0 comments hiiiiiiiiiiiiii

hrishi635 + 0 comments thanks!

astar250 + 0 comments [deleted]anuhosad + 0 comments Same solution in Javascript

function minimumAbsoluteDifference(n, arr) { arr.sort((a, b) => a - b); let min = Math.abs(arr[0] - arr[1]), diff; for(let i = 2; i < n; i++) { diff = Math.abs(arr[i] - arr[i-1]); if(diff < min) { min = diff; } } return min; }

Lalchetaketan022 + 0 comments Yes...This solution works. My concern is that does it ensure that minimum difference between sorted vector is possible combination as per example output case?

pczek + 0 comments Great hint, haven't thought about that. I try to keep in mind that sorted Arrays have certain characteristics.

tamim447 + 0 comments How i solve time limites..?

zhengyaojun1204 + 1 comment I love your idea!!! You made the question so easy!

tamim447 + 0 comments how??

MukulCode + 0 comments this was really helpful.

sai_shan + 0 comments Thanks, It was really helpful.. do u think using these hints is cheating ?

sridharbajpai + 0 comments can we get maximum difference from this method?

NiceBuddy + 0 comments A little diffrent C++ approch

#include <cmath> #include <limits> #include <set> #include <iostream> #include <algorithm> #include <iterator> using int64 = long long int; template<typename Iterator> constexpr auto getResult( Iterator begin, const Iterator end)-> int64 { // following is not working with GCC //using Type = typename std::decay<typename std::iterator_traits<Iterator>::difference_type>::type; //static_assert(std::is_same<Type, int64>::value, "wrong types"); // to make sure using Type = int64; Type ans{ std::numeric_limits<Type>::max() }; for (auto iter = std::next(begin); iter != end; ++iter) { ans = std::min(ans, std::abs(*iter - *std::prev(iter))); } return ans; } int main() { std::ios_base::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0); int64 n{}; std::cin >> n; std::multiset<int64> mySet; while (n--) { int64 temp{}; std::cin >> temp; mySet.insert(temp); } std::cout << ::getResult(mySet.begin(), mySet.end()) << std::endl; return 0; }

subhamraj4114 + 0 comments # C# Code

static int minimumAbsoluteDifference(int[] arr) { int n = arr.Length; Array.Sort(arr); int minAbsDiff = Math.Abs(arr[0] - arr[1]); for(int i = 1; i < n - 1; i++){ int tempDiff = Math.Abs(arr[i] - arr[i + 1]); if(tempDiff < minAbsDiff) minAbsDiff = tempDiff; } return minAbsDiff; }

bharathreddyspi + 0 comments But sorting for that much larger data set may give runtime errors in languages like c

lalithnani + 0 comments thanks

sumanconstantin + 0 comments No need in 2).

Min should always default to max.

In this example: int min = INT_MAX;

Then compare abs of all consecutive pairs to min.

BTANguyen + 1 comment Why this is under greedy algo ? What is the greedy property in this problem?

ggorlen + 0 comments Probably because if you locate some local minimum distance, that's also the global minimum until you find something better. In other words, if you find a minimum, that's optimal and you take it. In contrast, finding a shortest route in a graph doesn't work if you greedily always take the shortest route at every juncture, since sometimes taking a longer route in the short term offers a better path overall.

_sss1 + 3 comments Is it possible to solve it better than O (n log n)?

positivedeist_07 + 0 comments I was wondering the same. This requires the array to be sorted, which obviously leads to the complexity of O(n log n). I wonder if we can solve it by using other data structures (thus increasing the space complexity)

orancanoren + 3 comments Can't stop thinking the same. Well, actually we can sort the array in linear time using count sort (linear in terms of the range of elements in the array) and have a linear running time algorithm but it's not really elegant since we increase space complexity.

positivedeist_07 + 0 comments Yeah, but space doesnt matter. Obviously we would need more space to decrease the runtime.

positivedeist_07 + 2 comments Can this problem be solved without ever using any sorting algm?

orancanoren + 1 comment Well you could, by comparing each element with every other element but that'd result in O(n^2)

positivedeist_07 + 1 comment But that'd be like worse than O(n log n). Guess we could sort by count or radix or bucket to achieve O(n) in sorting

bak_karolek + 0 comments You can't achieve O(n) through bucket sort if you don't know if the input is random. In this problem it is not directly stated. If it was, bucket would seem to be a nice option indeed.

Radix works better for strings, sure longer than 10 digits. Constant factor for such sorting would be unnecessary big, make it slower than qsort.

And you have to be careful with count sort - its speed depends on range of numbers so, instead of O(n log n) (for qsort n = 10^5) you get O(n) (where n = ai = 10^9).

And, cause

- 10^5 * log(10^5) < 10^9
- log(10^5) < 10^4

then count works longer for big input.

Also, for input like {0, 10^9} count sort still needs O(10^9) time.

vishu006 + 0 comments Yes it could be solved in O(n) time, but would require enormous space ~ an array of 2*pow(10,9) locations.

Take the input

*temp*and store it in a location a[*temp*+1000000000]th location.Next iterate throough the array and find the closest occuring elements. Also, if any element occurs more than once,print 0.To further increase the process you can take min and max values during the input of the

*temp*. Now you would only have to iterate from min to max values present in the array. And if any element's counter crosses 1, break and output 0.However, this would

**not be recommended here**due to high space complexity.This has**great purposes in other problems**.

liamroche + 0 comments You could do an O(n) check to see if the range of the numbers was sufficiently small to make it possible for this to be better than using sorting. If you knew the differences of the numbers had a common factor, you could use this to shrink the range, but finding the GCD of two integers is probably O(log(max(abs(n1), abs(n2)))), so this only helps without additional information when the range of the integers is small compared to their number. In this situation (n values from m possibilities where m < n), the pigeon hole principle tells us immediately (O(1)) that the min distance is zero!

bertk + 0 comments This should do it without sorting. It is O(cn) for time and O(n) for space.

BUT, it times out on the last two input sets since the array values are very large(-10^9 < a < 10^9), while n < 10^5. This yields a constant that is larger than n.

If you have a domain with a much smaller range for a, it would make sense.

def minimumAbsoluteDifference2(n, arr): min_abs = abs(arr[0] - arr[1]) s = set(arr[:2]) for x in arr[2:]: for d in range(1, min_abs): if x + d in s or x - d in s: min_abs = d break s.add(x) return min_abs

dejno + 1 comment JavaScript version that I like and feel is readable and clean.

function minimumAbsoluteDifference(arr) { // Sort arr.sort(); let minDiff; // Loop through the consecutive pairs, if 0 return, else set min diff for (let i = 0; i < arr.length; i++) { let absDiff = Math.abs(arr[i+1] - arr[i]); if (!minDiff || absDiff < minDiff) minDiff = absDiff; if (minDiff === 0) return 0; } return minDiff; }

ding_randy + 1 comment For others reading this solution I just want to comment on using arr.sort() in JS since this has burned me before.

By default, Javascript's Array.prototype.sort will sort elements in

**lexicographical order**, which means sorting [2, 4, 30] will convert the integers to strings and produce [2, 30, 4] (since '3' comes before '4'). To properly sort integers a custom compare function should be passed in. I.e. arr.sort( ( a, b ) => a - b ).The default sort order is built upon converting the elements into strings, then comparing their sequences of UTF-16 code units values.

Somehow none of the test cases triggered this exact scenario and the posted solution indeed passes all tests, but feel free to experiment with various inputs on your own, e.g. [2, 4, 30] (should return 2, but would return 26 using the default sort).

dejno + 0 comments This is a great callout.

acfromspace + 1 comment My Python3 solution:

def minimumAbsoluteDifference(arr): arr.sort() return min([abs(arr[counter+1] - arr[counter]) for counter in range(len(arr)-1)])

I'm not really sure how it works, but if you sort the data structure, finding the minimum is all about comparing consectutive indexes to each other instead of to every index. After this, we do our usual absolute value and minimum value.

hubrando + 0 comments I did basically your solution but in a more beginner friendly, readable way.

# Complete the minimumAbsoluteDifference function below. def minimumAbsoluteDifference(arr): min_abs_diff = sys.maxsize tmp_result = 0 arr.sort() for i in range (len(arr) - 1): tmp_result = abs(arr[i] - arr[i + 1]) if tmp_result < min_abs_diff: min_abs_diff = tmp_result return min_abs_diff

marinskiy + 1 comment Here is

**Python 3**solution from my HackerrankPractice repository:_ = input() arr = sorted(map(int, input().split())) diff = 2*10**9 for i in range(1, len(arr)): diff = min(diff, arr[i] - arr[i-1]) print(diff)

Feel free to ask if you have any questions :)

rmwthorne + 0 comments Thank you for sharing - I was thinking along the same lines. Is there any reason why you chose 2 billion as your upper bound for the difference? Why not

`math.inf`

?

blade_kim + 0 comments Swift

func minimumAbsoluteDifference(arr: [Int]) -> Int { var value = Int.max let list = arr.sorted() for i in 0..<arr.count-1 { value = min( value, abs( list[i] - list[i+1] )) } return value }

ankushrasgon07 + 0 comments return(min([abs(x[0]-x[1]) for x in combinations(arr,2)])) this one line giving me timeout cases

nidhi_bhushan123 + 0 comments def minimumAbsoluteDifference(arr): arr.sort() min_distance=sys.maxsize for i in range(len(arr)-1): distance = abs(arr[i]-arr[i+1]) if distance<min_distance: min_distance=distance return min_distance

vporta7 + 0 comments Python 3

def minimum_absolute_difference(arr): n = len(arr) arr = sorted(arr) r = [] for i in range(n-1): r.append(abs(arr[i]-arr[i+1])) return min(r)

Sort 254 Discussions, By:

Please Login in order to post a comment