Find the difference less than the average in an unsorted array?
Step 1: Use Branch Sort . Don't sort individual buckets.
It should be pretty obvious what to do next, and how to sort the buckets.
source to share
-
Number of buckets =
2n
.in each bucket =
(min + k((max-min)/2n)) <= value < (min + (k+1)((max-min)/2n)).
0 <= k <2n
Range of each bucket =
((max-min)/2n)
-
Assign each item to buckets. Don't sort inside the bucket.
-
If any bucket has more than 1 item, the maximum possible difference between them
((max-min)/2n)
. Hence, you have your answer. -
If any two consecutive buckets are greater than zero, each has a maximum difference between
((max-min)/2n)*2 = ((max-min)/n)
. Hence, you have your answer.
source to share
The correct question should be: in the array A = [a0, a2, .. an] find two elements a, b such that the difference between them is less than or equal to: (Mm) / n> | a - b | where M = max (A) and m = min (A).
Ill's solution suggests using quickSelect, O (n) time complexity pending. its actual worst case is O (n ^ 2). This is a tradeoff because most of the time it's O (n), but requires O (1) space complexity (assuming quickSelect is iteratively implemented and my pseudo code is implemented with a while loop instead of recursion).
Basic idea: at each iteration, we find the median quickSelect function if |max - medianValue | > |min - medianValue |
|max - medianValue | > |min - medianValue |
we know what we should look for in the left side of the array. This is because we have the same number of items on both sides, but the median is closer to the minimum, so there should be items with less difference between them. Otherwise, we must search on the right side.
every time we do this, we know that the new high or low of the subArray should be the median. we continue searching, dividing the size of the arrays by 2 each time.
pending runtime proof: suppose each iteration over n elements takes c * n + d time. thus we have:
(cn + d) + 0.5 (cn + d) + 0.25 (c * n + d) + ... + (1 / log_ {2} (n)) (cn + d) <=
<= (1 + 0.5 + 0.225 + ....) D + (c * n + 0.5 * cn + ....) = (1 + 0.5 + 0.225+ .. ..) D + cn (1 + 0.5 +0. 25 + ....) =
= 2 * d +2 * c * n
that we have O (n) pending.
pseudocode using recursion:
run(arr):
M = max(arr)
m = min(arr)
return findPairBelowAverageDiff(arr,0,arr.length,min,max)
findPairBelowAverageDiff(arr, start, end, min, max) :
if start + 1 < end:
medianPos = start + (end - start) / 2
// median that is between start and end in the arr.
quickSelect(arr, start, medianPos, end)
if max - arr[medianPos] > arr[medianPos] - min:
return findPairBelowAverageDiff(arr, start, medianPos,
min, arr[medianPos])
else :
return findPairBelowAverageDiff(arr, medianPos,
end, arr[medianPos], max);
else :
return (arr[start], arr[start + 1])
source to share