Maximum gap

Array Sorting Bucket Sort Radix Sort

51.5% acceptance

Jan 12, 2026

3546

440

Given an integer array nums, return the maximum difference between two successive elements in its sorted form. If the array contains less than two elements, return 0. You must write an algorithm that runs in linear time and uses linear extra space.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_gap(mut nums: Vec<i32>) -> i32 {
    if nums.len() < 2 {
      return 0;
    }
    
    let max_num = *nums.iter().max().unwrap() as u32;
    let mut exp = 1u32;
    
    while max_num / exp > 0 {
      Self::count_sort(&mut nums, exp);
      exp *= 10;
    }
    
    let mut max_gap = 0;
    for i in 1..nums.len() {
      max_gap = max_gap.max((nums[i] - nums[i - 1]) as i32);
    }
    
    max_gap
  }
  
  fn count_sort(nums: &mut Vec<i32>, exp: u32) {
    let mut output = vec![0; nums.len()];
    let mut count = vec![0; 10];
    
    for &num in nums.iter() {
      let index = ((num as u32 / exp) % 10) as usize;
      count[index] += 1;
    }
    
    for i in 1..10 {
      count[i] += count[i - 1];
    }
    
    for i in (0..nums.len()).rev() {
      let index = ((nums[i] as u32 / exp) % 10) as usize;
      output[count[index] - 1] = nums[i];
      count[index] -= 1;
    }
    
    *nums = output;
  }
}