This does seem hard and I can't figure a way to attack it without that extra logN. It can be solved in order N EXPECTED time but not true O(N) limits. (Interesting: the tougher 2D generalization of the problem, finding 2 points that are closest in a 2D plane, is O(n Log n) but also has an expected order N randomized algorithm. See for example the Kleinburg/Tardos textbook.)
These are integers so it's possible to use a O(n) radix sort! So sort the numbers, then scan down the list and look at the pairwise differences, return the largest.
If the numbers are reals, I think O(n log n) is the true limit. But computer integers or 32/64 bit floats are sortable in O(n) so this will work.
Good puzzle, I had given up. But that "integer" clue in the problem description was key.
this is difficult
ReplyDelete1. Use partiting step from quick sort
ReplyDelete2. compare [L/2 + 1] - [L/2] or [L/2] - [L/2 - 1]
This does seem hard and I can't figure a way to attack it without that extra logN. It can be solved in order N EXPECTED time but not true O(N) limits. (Interesting: the tougher 2D generalization of the problem, finding 2 points that are closest in a 2D plane, is O(n Log n) but also has an expected order N randomized algorithm. See for example the Kleinburg/Tardos textbook.)
ReplyDeletevstepanov, that requires you to descend recursively into both halves of the partition, making it O(n log n).
ReplyDeleteGot it!
ReplyDeleteThese are integers so it's possible to use a O(n) radix sort! So sort the numbers, then scan down the list and look at the pairwise differences, return the largest.
If the numbers are reals, I think O(n log n) is the true limit. But computer integers or 32/64 bit floats are sortable in O(n) so this will work.
Good puzzle, I had given up. But that "integer" clue in the problem description was key.
Can we make any assumptions about the numbers in the array? like possible range of values?
ReplyDeleteCan you make any assumptions about the integer range?
ReplyDelete