We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

Don't append the diffs. You are just incresing the space complexity. Also you are taking the min(diffs). In the background this is another for loop, so your time complexity increses by O(n).

Just take a variable, maybe name it diffs. Every time you encounter a new min, update the diffs, and finally return it.

bcoz, sorting of array will bring small value element near, thus their diff also min.

suppose if didn't apply sort..
ex.
n = 4
arr = 2 34 68 1
in this case 2 and 1 are not near so their diff will not be calaculate by the loop(as per ur logic).

In this case, if the "list by comprehension" to which you refer is presumably that which is inside the min function, then your assertion is false.

Here in Python3, a generator is being passed to the min function, so no list is being created in memory for it. Elements are being discovered through lazy evaluation of the formula. The minimum is a greedy operation running over the indices i, so it does not store the previous values a[i+1]-a[i] as it proceeds forward. It just finds the minimum up to that point when the i-th term is considered.

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)

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.

#include<cmath>#include<limits>#include<set>#include<iostream>#include<algorithm>#include<iterator>usingnamespacestd;#define ll long long intintmain(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);lln,ans=numeric_limits<ll>::max();cin>>n;multiset<ll>mySet;for(autoi=0;i<n;++i){lltemp=0;cin>>temp;mySet.insert(temp);}for(autoitr=mySet.begin();itr!=mySet.end();++itr)if(itr!=mySet.begin()){lla=*(itr--);llb=*(itr++);ans=min(ans,abs(a-b));}cout<<ans<<endl;return0;}

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.

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.

//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;

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:

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?

#include<cmath>#include<limits>#include<set>#include<iostream>#include<algorithm>#include<iterator>usingint64=longlongint;template<typenameIterator>constexprautogetResult(Iteratorbegin,constIteratorend)->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 sureusingType=int64;Typeans{std::numeric_limits<Type>::max()};for(autoiter=std::next(begin);iter!=end;++iter){ans=std::min(ans,std::abs(*iter-*std::prev(iter)));}returnans;}intmain(){std::ios_base::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);int64n{};std::cin>>n;std::multiset<int64>mySet;while(n--){int64temp{};std::cin>>temp;mySet.insert(temp);}std::cout<<::getResult(mySet.begin(),mySet.end())<<std::endl;return0;}

// sort array
arr.sort((a, b) => a - b)
// consider a min
let min = Math.abs(arr[0] - arr[1])
for(let i = 1; i < arr.length - 1; i++) {
// calculate absolute between absolutes
// minimum difference is between adjacent elements in a sorted array
let m = Math.abs(arr[i] - arr[i+1])
if(m < min) {
min = m
}
}
return min

## Minimum Absolute Difference in an Array

You are viewing a single comment's thread. Return to all 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.

Yeah, it was pretty easy after reading your comment.

Check for duplicates helps to avoid unnecessary computations.

This is relevant for one of the tests.

to avoid even more unnecessary computations:

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

ha ha! wonderful

You can also abort when diff is zero to pass the test.

Not sure how relevant, this passes all tests:

Don't append the diffs. You are just incresing the space complexity. Also you are taking the min(diffs). In the background this is another for loop, so your time complexity increses by O(n).

Just take a variable, maybe name it diffs. Every time you encounter a new min, update the diffs, and finally return it.

bcoz, sorting of array will bring small value element near, thus their diff also min.

suppose if didn't apply sort.. ex. n = 4 arr = 2 34 68 1 in this case 2 and 1 are not near so their diff will not be calaculate by the loop(as per ur logic).

My

2-line Python3solution (passes all testcases) was similar but no`abs`

or`append`

.That list by comprehension is equivalent to building it by appending. The space complexity is the same.

In this case, if the "list by comprehension" to which you refer is presumably that which is inside the

`min`

function, then your assertion is false.Here in

Python3, ageneratoris being passed to the`min`

function, so no list is being created in memory for it. Elements are being discovered through lazy evaluation of the formula. The minimum is a greedy operation running over the indices`i`

, so it does not store the previous values`a[i+1]-a[i]`

as it proceeds forward. It just finds the minimum up to that point when the`i`

-th term is considered.it's really nice!

you are not considering all pairs, zip is not useful in this case

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)

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.

Here is your approach in C++:

without sorting: using multiset;

And that's because multiset insert does the sort work.

fuke

What does that word mean?

Why should we consider only consecutive pairs? It can be any two elements from the array right?

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.

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.

//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());

}

this will only work for checking consecutive elements diff not ANY

forr that we are doing sort(vec.begin(), vec.end());

The consecutive elements give the minimal than "any"

C++ STL

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

why you put *min_element(begin(arr)+1, end(arr))

why not *min_element(begin(arr), end(arr));

The element at begin(arr) is the first element in the sorted array (see http://www.cplusplus.com/reference/numeric/adjacent_difference/?kw=adjacent_difference for details on how this works). As a result, begin(arr)+1 points to the first absolute difference between two elements.

Why do you sort it? In what way does it help?

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

ok thanks!

And the sign never changes

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:

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.

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

hiiiiiiiiiiiiii

thanks!

Same solution in Javascript

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?

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

How i solve time limites..?

which sort is best? insertion?

Best sort asymptotically is Merge Sort, with a Big O(nlogn). Insertion has a Big O (n^2) which is far worse when dealing with large data sets.

we need swap.. using merge is it pssible

I love your idea!!! You made the question so easy!

how??

this was really helpful.

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

can we get maximum difference from this method?

Just find min and max from arr and find their absolute difference.

A little diffrent C++ approch

## C# Code

thanks

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.

Thanks your guidence lead to Better solution !!

public class Solution {

Thanks for the hint

Javascript solution:

function minimumAbsoluteDifference(arr) {

}

I ended up with this approach as well (except the 2nd step where I just pick a very large num), though I don't think this is a greedy algorithm.