Gamified challenge · Bucket sort
scores holds whole-number scores (0 or more, in no order, repeats allowed). Imagine them sorted: the gap between two neighbours is the bigger minus the smaller. Return the largest gap.
With fewer than two scores there is no gap, so return 0. Write maxGap(scores); for [3, 6, 9, 1] the sorted order is 1, 3, 6, 9 and the answer is 3.
Sorting works, but try for O(n): put the scores into n − 1 equal-width buckets between the minimum and maximum. The largest gap is at least the bucket width, so it always runs from one non-empty bucket's maximum to the next non-empty bucket's minimum.
This game is part of the paid plans. Sign in, then pick a plan to write your answer, watch it play out, and step through the algorithm with its guide.
Sign in with Google