Find Largest Adjacent Sorted Difference
Company: Waymo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an unsorted array of integers `nums`, compute the largest difference between two consecutive elements after the array is sorted in ascending order.
Return `0` if the array has fewer than two elements.
Your algorithm must run in `O(n)` time and use `O(n)` extra space. A comparison-based sort is not allowed.
**Example 1:**
```text
Input: nums = [3, 6, 9, 1]
Output: 3
Explanation: After sorting, nums becomes [1, 3, 6, 9]. The consecutive differences are 2, 3, and 3, so the answer is 3.
```
**Example 2:**
```text
Input: nums = [10]
Output: 0
```
**Constraints:**
- `1 <= nums.length <= 100000`
- `0 <= nums[i] <= 1000000000`
- The expected solution should use a bucket-based linear-time approach.
Quick Answer: This question evaluates skills in array processing, linear-time algorithm design, and application of bucket-based, non-comparison techniques for computing maximum adjacent gaps after sorting.
Given an unsorted array of integers nums, compute the largest difference between two consecutive elements after the array is sorted in ascending order.
Return 0 if the array has fewer than two elements.
Your algorithm must run in O(n) time and use O(n) extra space. A comparison-based sort is not allowed, so the expected approach is to use buckets and the pigeonhole principle.
Constraints
- 1 <= len(nums) <= 100000
- 0 <= nums[i] <= 1000000000
- The expected solution must run in O(n) time and use O(n) extra space without using a comparison-based sort
Examples
Input: ([3, 6, 9, 1],)
Expected Output: 3
Explanation: After sorting, the array is [1, 3, 6, 9]. The consecutive differences are 2, 3, and 3, so the largest is 3.
Input: ([10],)
Expected Output: 0
Explanation: There is only one element, so there are no consecutive pairs.
Hints
- If there are n numbers between a global minimum and maximum, think about dividing the range into buckets of width based on (max - min) / (n - 1).
- You do not need to sort the contents of each bucket. Track only the minimum and maximum value in each non-empty bucket, because the largest gap must occur between buckets.