medium Maximum Gap

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 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

class Solution {

  public int findmaximumGap(int[] nums) {
    // If the array is null or has fewer than 2 elements, return 0.
    if (nums == null || nums.length < 2) {
      return 0;
    }

    // Find the maximum value in the array to determine the number of digits
    int maxValue = Integer.MIN_VALUE;
    for (int number : nums) {
      maxValue = Math.max(maxValue, number);
    }

    int digitPlace = 1; // Start with the least significant digit
    int base = 10; // We're sorting by decimal digits
    int[] buffer = new int[nums.length]; // Auxiliary array for sorting

    // Perform radix sort based on each digit
    while (maxValue / digitPlace > 0) {
      int[] count = new int[base]; // Count array for digits (0-9)

      // Count occurrences of each digit in the current digit place
      for (int number : nums) {
        count[(number / digitPlace) % 10]++;
      }

      // Accumulate the count array to get positions of elements
      for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
      }

      // Build the output array by placing elements in the correct position
      for (int i = nums.length - 1; i >= 0; i--) {
        buffer[--count[(nums[i] / digitPlace) % 10]] = nums[i];
      }

      // Copy the sorted nums back into the original array
      System.arraycopy(buffer, 0, nums, 0, nums.length);

      // Move to the next digit place
      digitPlace *= 10;
    }

    // Calculate the maximum gap between consecutive elements
    int maximumGap = 0;
    for (int i = 0; i < nums.length - 1; i++) {
      maximumGap = Math.max(nums[i + 1] - nums[i], maximumGap);
    }

    return maximumGap;
  }

  // Main method to test the function
  public static void main(String[] args) {
    Solution solution = new Solution();

    int[] nums1 = { 10, 50, 20, 90, 60 };
    System.out.println("Maximum Gap: " + solution.findmaximumGap(nums1)); // Output: 30

    int[] nums2 = { 5, 100, 1, 50, 9 };
    System.out.println("Maximum Gap: " + solution.findmaximumGap(nums2)); // Output: 50

    int[] nums3 = { 300, 10, 200, 100, 600 };
    System.out.println("Maximum Gap: " + solution.findmaximumGap(nums3)); // Output: 300
  }
}

Complexity Analysis

Time Complexity

• Finding the maximum value: The first loop iterates through all elements of the array to find the maximum value. This takes time, where n is the number of elements in the array.

• Radix Sort: The radix sort processes each digit of the numbers. Since the maximum number has d digits, and each digit processing involves counting and placing the numbers, the time complexity is , where k is the base (10 in this case). Since k is a constant (10), the complexity can be simplified to . The value of d is logarithmic with respect to the maximum value, i.e., d = log(maxValue).

• Finding the maximum gap: After sorting, we need to find the maximum gap by iterating through the sorted array. This takes time.

• Overall Time Complexity: Therefore, the overall time complexity is , which is almost equal to .

Space Complexity

• Auxiliary Array (buffer): We use an auxiliary array buffer of the same size as the input array, resulting in space.

• Count Array: The count array has a constant size of 10 (for base 10), which is space.

• Overall Space Complexity: The total space complexity is .