Problem Statement

Given an integer array nums, return the largest difference between any two consecutive elements in the sorted form of nums. If the array has less than two elements, return 0.

Note: Your solution should run in linear time and use linear extra space.

Examples

Example 1:

• Input: nums = [10, 50, 20, 90, 60]
• Expected Output: 30
• Justification: When sorted, the array becomes [10, 20, 50, 60, 90]. The largest gap is between 20 and 50 or 60 and 90, which is 30.

Example 2:

• Input: nums = [5, 100, 1, 50, 9]
• Expected Output: 50
• Justification: The sorted array is [1, 5, 9, 50, 100]. The largest gap is between 50 and 100, which is 50.

Example 3:

• Input: nums = [300, 10, 200, 100, 600]
• Expected Output: 300
• Justification: After sorting, the array becomes [10, 100, 200, 300, 600]. The largest gap is between 300 and 600, which is 300.

Constraints:

• 1 <= nums.length <= 10⁵
• 0 <= nums[i] <= 10⁹

Solution

To solve this problem, a good approach is to use radix sort to sort the array and then find the maximum difference between consecutive elements. Radix sort is a non-comparative sorting algorithm that has a time complexity of O(n) for fixed-length integers, which makes it ideal for this problem. After sorting, we need to make a simple iteration through the array to calculate the maximum gap between consecutive elements.

Step-by-Step Algorithm

1. Check for Valid Input:

   • If the array numbers is null or has fewer than 2 elements, return 0. This ensures that we do not attempt to find a gap when there are not enough elements.

2. Find the Maximum Value:

   • Traverse through the array to find the maximum value, maxValue. This helps us determine the number of digits to sort by using radix sort.

3. Initialize Variables:

   • Set digitPlace = 1 (start with the least significant digit).
   • Set base = 10 (decimal system, so digits range from 0 to 9).
   • Create an auxiliary array buffer with the same length as numbers. This will hold intermediate sorted results during the sort.

4. Counting Sort (for each digit place):

   • 4.1 Create the Count Array:

     • Initialize a count array of size 10 (for digits 0-9), initially filled with zeros. This array will store the frequency of each digit at the current digitPlace.

   • 4.2 Count the Occurrences of Digits:

     • Iterate over each element in numbers. For each number, calculate the digit at the current digitPlace using (number / digitPlace) % 10, and increment the corresponding index in the count array.

   • 4.3 Accumulate the Count Array:

     • Transform the count array so that each index stores the cumulative count of digits up to that index. This helps in placing the numbers in the correct positions during sorting.

   • 4.4 Build the Output Array:

     • Iterate over the numbers array in reverse order to ensure the stability of the sorting algorithm.
       • For each element in numbers, find the digit at the current digitPlace.
       • Use the count array to determine the correct position for the element in the buffer array. Subtract 1 from the value in the count array at the index corresponding to the digit, and use this as the position index in the buffer array.
       • Place the element in buffer and decrement the corresponding value in the count array to update the position for the next element with the same digit.

   • 4.5 Copy the Sorted Array:

     • Copy the sorted array from buffer back to numbers. This prepares the array for sorting by the next digit place in the next iteration.

   • 4.6 Move to the Next Digit Place:

     • Multiply digitPlace by 10 to move from the current digit place (e.g., units) to the next (e.g., tens).

5. Calculate Maximum Gap:

   • After sorting, iterate through the sorted array numbers to calculate the difference between consecutive elements. Track the maximum difference encountered.

6. Return the Result:

   • Return the maximum gap found between consecutive elements in the sorted array.

Algorithm Walkthrough

Let's walk through the algorithm step-by-step using the input array [10, 50, 20, 90, 60].

1. Initial Setup:

   • Array: [10, 50, 20, 90, 60]
   • maxValue after traversal: 90
   • Initialize digitPlace = 1, base = 10, and buffer = [0, 0, 0, 0, 0]

2. First Pass (Units Place - digitPlace = 1):

   • Create the Count Array:

     • Initialize count to [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

   • Count the Occurrences:

     • Process 10: (10 / 1) % 10 = 0 → count[0]++ → count = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
     • Process 50: (50 / 1) % 10 = 0 → count[0]++ → count = [2, 0, 0, 0, 0, 0, 0, 0, 0, 0]
     • Process 20: (20 / 1) % 10 = 0 → count[0]++ → count = [3, 0, 0, 0, 0, 0, 0, 0, 0, 0]
     • Process 90: (90 / 1) % 10 = 0 → count[0]++ → count = [4, 0, 0, 0, 0, 0, 0, 0, 0, 0]
     • Process 60: (60 / 1) % 10 = 0 → count[0]++ → count = [5, 0, 0, 0, 0, 0, 0, 0, 0, 0]

   • Accumulate the Count Array:

     • Resulting count array: [5, 5, 5, 5, 5, 5, 5, 5, 5, 5]

   • Build the Output Array:

     • Process 60: (60 / 1) % 10 = 0 → Place 60 at buffer[4] → count[0]-- → count = [4, 5, 5, 5, 5, 5, 5, 5, 5, 5]
     • Process 90: (90 / 1) % 10 = 0 → Place 90 at buffer[3] → count[0]-- → count = [3, 5, 5, 5, 5, 5, 5, 5, 5, 5]
     • Process 20: (20 / 1) % 10 = 0 → Place 20 at buffer[2] → count[0]-- → count = [2, 5, 5, 5, 5, 5, 5, 5, 5, 5]
     • Process 50: (50 / 1) % 10 = 0 → Place 50 at buffer[1] → count[0]-- → count = [1, 5, 5, 5, 5, 5, 5, 5, 5, 5]
     • Process 10: (10 / 1) % 10 = 0 → Place 10 at buffer[0] → count[0]-- → count = [0, 5, 5, 5, 5, 5, 5, 5, 5, 5]
     • buffer after placement: [10, 50, 20, 90, 60]

   • Copy the Output Array:

     • Copy buffer back to numbers: [10, 50, 20, 90, 60]

   • Move to the Next Digit Place:

     • Update digitPlace = 10

3. Second Pass (Tens Place - digitPlace = 10):

   • Create the Count Array:

     • Initialize count to [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

   • Count the Occurrences:

     • Process 10: (10 / 10) % 10 = 1 → count[1]++ → count = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
     • Process 50: (50 / 10) % 10 = 5 → count[5]++ → count = [0, 1, 0, 0, 0, 1, 0, 0, 0, 0]
     • Process 20: (20 / 10) % 10 = 2 → count[2]++ → count = [0, 1, 1, 0, 0, 1, 0, 0, 0, 0]
     • Process 90: (90 / 10) % 10 = 9 → count[9]++ → count = [0, 1, 1, 0, 0, 1, 0, 0, 0, 1]
     • Process 60: (60 / 10) % 10 = 6 → count[6]++ → count = [0, 1, 1, 0, 0, 1, 1, 0, 0, 1]

   • Accumulate the Count Array:

     • Resulting count array: [0, 1, 2, 2, 2, 3, 4, 4, 4, 5]

   • Build the Output Array:

     • Process 60: (60 / 10) % 10 = 6 → Place 60 at buffer[3] → count[6]-- → count = [0, 1, 2, 2, 2, 3, 3, 4, 4, 5]
     • Process 90: (90 / 10) % 10 = 9 → Place 90 at buffer[4] → count[9]-- → count = [0, 1, 2, 2, 2, 3, 3, 4, 4, 4]
     • Process 20: (20 / 10) % 10 = 2 → Place 20 at buffer[1] → count[2]-- → count = [0, 1, 1, 2, 2, 3, 3, 4, 4, 4]
     • Process 50: (50 / 10) % 10 = 5 → Place 50 at buffer[2] → count[5]-- → count = [0, 1, 1, 2, 2, 2, 3, 4, 4, 4]
     • Process 10: (10 / 10) % 10 = 1 → Place 10 at buffer[0] → count[1]-- → count = [0, 0, 1, 2, 2, 2, 3, 4, 4, 4]
     • buffer after placement: [10, 20, 50, 60, 90]

   • Copy the Output Array:

     • Copy buffer back to numbers: [10, 20, 50, 60, 90]

4. Calculate Maximum Gap:

   • Calculate Differences:
     • 20 - 10 = 10
     • 50 - 20 = 30 (maximum gap so far)
     • 60 - 50 = 10
     • 90 - 60 = 30 (matches current maximum gap)
   • Maximum Gap: 30

5. Final Result:

   • The maximum gap for [10, 50, 20, 90, 60] is 30.

Code