Menu
Given an unsorted integer array, and without making any assumptions on the numbers in the array:
Is it possible to find two numbers whose difference is minimum in O(n) time?
Edit: Difference between two numbers a, b is defined as abs(a-b)
502
function FindMin(arr) { //sort the array in increasing order arr. sort((a,b) => { return a-b; }); let min = arr[1]-arr[0]; let n = arr. length; for (var i=0;i<n;i++) { let m = arr[i+1] - arr[i]; if(m < min){ m = min; } } return m; // minimum difference. }
Subtract the smallest number from the largest number in the pair, this will generate the interval. Store in a variable the difference generated by every operation and update it only if the result is lower than the previous one, once it ends, the variable will store the smallest interval, which in this case is 2.
You can use array#map . For the first index value subtract from 0 and for other indexes, subtract from the previous number.
Find smallest and largest element in the list. The difference smallest-largest will be minimum.
If you're looking for nonnegative difference, then this is of course at least as hard as checking if the array has two same elements. This is called element uniqueness problem and without any additional assumptions (like limiting size of integers, allowing other operations than comparison) requires >= n log n time. It is the 1-dimensional case of finding the closest pair of points.
170
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
