Find the Largest Sorted-Neighbor Gap in Linear Time
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Return the largest difference between successive values in the array's sorted order. If fewer than two values are present, return 0. The algorithm must use linear time and linear extra space.
```cpp
int maximumGap(vector<int>& nums);
```
### Examples
```text
Input: nums = [14,2,9,3]
Output: 6
```
Sorted order is 2,3,9,14, whose gaps are 1,6,5.
```text
Input: nums = [6,6]
Output: 0
```
### Constraints
- Length is between 1 and 100000.
- Values lie between 0 and 1000000000, inclusive.
Overview: Compute the maximum sorted-neighbor gap in linear time using width-bounded bucket extrema.