On Sep 1, 7:05 am, ankur aggarwal ankur.mast@gmail.com wrote:
given a array of length n. find 2 number such that their differnce is
minimum.
As already pointed out sorting and then comparing adjacent elements
gives you an O(n log n) algorithm.
If you have a likelyhood of duplicates
On Sep 1, 8:02 pm, Ramaswamy R ramaswam...@gmail.com wrote:
Brute force, pick all combinations and keep track of minimum difference.
Complexity: O(n^2) - (n-1)+(n-2)+(n-3) ... 1
A little better, use any of the O(nlog n) sorting algorithm. In O(n) compare
adjacent pairs and find the minimum
While sorting itself, algorithm can keep track of minimum difference between
two consecutive elements found so far and the elements. This way time
complexity is same as time complexity of sorting algorithm.
Space complexity also I think its O(1).
On Wed, Sep 2, 2009 at 6:00 PM, Ralph Boland
It won't work for following case
If suppose array contains the following integers
10 5 1 15 9
then according to you answer would be diff = |1-5| = 4
but correct answer is diff = |9-10| = 1
Thanks and Regards
Amit Chauhan
http://web.iiit.ac.in/~chauhan
Mobile : +91-9966347645
Y! IM :
If the range of numbers is known, sort the array using radix sort and
compare difference of adjacent elements.
On Sep 2, 2:33 pm, Varun S V varun...@gmail.com wrote:
Sorry this doesnt work. The difference between any other two sets can be
lesser than the difference between two min numbers.
Hi,
I think we can use Min Heap Algorithm right!
On Wed, Sep 2, 2009 at 3:03 PM, Varun S V varun...@gmail.com wrote:
Sorry this doesnt work. The difference between any other two sets can be
lesser than the difference between two min numbers.
On Wed, Sep 2, 2009 at 2:57 PM, Varun S V
@Varun S VIt wont work for this 1 3 4 5
2009/9/2 Varun S V varun...@gmail.com
Since we difference between two minumum elements should suffice, how about
finding the min and second minimum element in the array in single scan and
returning their difference. This should take not more than O(N)
Brute force, pick all combinations and keep track of minimum difference.
Complexity: O(n^2) - (n-1)+(n-2)+(n-3) ... 1
A little better, use any of the O(nlog n) sorting algorithm. In O(n) compare
adjacent pairs and find the minimum difference. Complexity O(nlog n).
On Tue, Sep 1, 2009 at 6:05 AM,
one simple brute force method I see is that sort the array with the best
possible time complexity and then take the difference between the two middle
most if n is even or compare the difference between the adjacent and middle
element and take the lower is n is odd.
On Tue, Sep 1, 2009 at 6:35 PM,
Sort the array and find the minimum of difference of adjacent values of the
sorted array.
Time Complexity : O(nlogn), Space Complexity : O(1)
On Tue, Sep 1, 2009 at 6:35 PM, ankur aggarwal ankur.mast@gmail.comwrote:
given a array of length n. find 2 number such that their differnce is
10 matches
Mail list logo
