int maximumGap(vector<int> arr) {
    if(arr.empty() || arr.size() < 2) return 0;
    int size = arr.size();
    int maxNum = *max_element(arr.begin(), arr.end());
    int minNum = *min_element(arr.begin(), arr.end());

    int gap = (maxNum - minNum - 1) / (size - 1) + 1;

    vector<int> bucketsMin(size - 1, INT_MAX);
    vector<int> bucketsMax(size - 1, INT_MIN);

    int buckInd;
    for (int i = 0; i < size; i++) {
      if (arr[i] != maxNum && arr[i] != minNum) {
          buckInd = (arr[i] - minNum) / gap;
          bucketsMin[buckInd] = min(bucketsMin[buckInd], arr[i]);
          bucketsMax[buckInd] = max(bucketsMax[buckInd], arr[i]);
      }
    }
    int result = INT_MIN;
    int previous = minNum;
    for (int i = 0; i < size - 1; i++) {
      if (bucketsMin[i] == INT_MAX && bucketsMax[i] == INT_MIN) continue;
      result = max(maxGap, bucketsMin[i] - previous);
      previous = bucketsMax[i];
    }
    result = max(result, maxNum - previous);
    return result;
}