Widest Gap When Sorted

Medium

You get an array of non-negative integers values. Imagine it sorted in ascending order. Return the largest difference between two neighbouring elements in that order. If the array has fewer than two elements, return 0. Sorting in O(n log n) solves it right away. Try to do it in linear time with linear extra space.

Example 1

values=[14, 2, 30, 7] → 16

Sorted: [2, 7, 14, 30]. The gaps are 5, 7 and 16, so the widest is 16.

Example 2

values=[42] → 0

There are no neighbours, so the answer is 0.

Example 3

values=[5, 5, 6, 5] → 1

Constraints

1 ≤ len(values) ≤ 10⁵
0 ≤ values[i] ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Bucket Sort Radix Sort Sorting

Similar problems

Hand-Rolled Sort Medium Most Common Values Medium Most Searched Words Medium K-th Code by Its Last Digits Medium Close Readings Nearby Hard

Input

values=[14, 2, 30, 7]

Expected

Run checks the first 3 tests in your browser. Submit checks all 126 tests on the server, hidden ones included.