164. Maximum Gap

leetcode medium

#array#csharp#intervals#leetcode#math#medium#sort

Task

Дан массив целых чисел nums. Верните максимальную разницу между двумя последовательными элементами в его отсортированной форме. Если массив содержит менее двух элементов, верните 0.

C# solution

matched/original

public class Solution {
    public int MaximumGap(int[] nums) {
        if (nums == null ||
            nums.Length < 2) 
            return 0;
        Array.Sort(nums);
        int maxGap = 0;
        for (int i = 0; i < nums.Length - 1; i++)
            maxGap = Math.Max(nums[i + 1] - nums[i], maxGap);
        return maxGap;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaximumGap(vector<int>& nums) {
        if (nums == null ||
            nums.size() < 2) 
            return 0;
        sort(nums.begin(), nums.end());
        int maxGap = 0;
        for (int i = 0; i < nums.size() - 1; i++)
            maxGap = max(nums[i + 1] - nums[i], maxGap);
        return maxGap;
    }
}

Java solution

matched/original

public class Solution {
    public int maximumGap(int[] nums) {
        if (
            nums == null || nums.length < 2
        ) return 0; 
        Arrays.sort(nums);

        int maxGap = 0;

        for (int i = 0; i < nums.length - 1; i++) maxGap = Math.max(
            nums[i + 1] - nums[i],
            maxGap
        );

        return maxGap;
    }
}

JavaScript solution

matched/original

var maximumGap = function (nums) {
    if (nums == null || nums.length < 2)
        return 0;

    nums.sort((a, b) => a - b)

    var maxGap = 0;

    for (var i = 0; i < nums.length - 1; i++)
        maxGap = Math.max(nums[i + 1] - nums[i], maxGap);

    return maxGap;
};

Python solution

matched/original

class Solution:
    def maximumGap(self, nums):
        if (
            nums is None or len(nums) < 2
        ): 
            return 0

        nums.sort()  
        maxGap = 0

        for i in range(len(nums) - 1):
            maxGap = max(nums[i + 1] - nums[i], maxGap)

        return maxGap

Go solution

matched/original

func maximumGap(nums []int) int {
    if len(nums) < 2 { 
        return 0
    }

    sort.Ints(nums)
    maxGap := 0

    for i := 0; i < len(nums)-1; i++ {
        diff := nums[i+1] - nums[i]
        if diff > maxGap {
            maxGap = diff
        }
    }

    return maxGap
}

Explanation

Algorithm

Пример:

Input: nums = [3,6,9,1]

Output: 3

Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3.

👨‍💻

Алгоритм:

1️⃣

Инициализация:

Определите минимальное и максимальное значения в массиве для расчета возможного максимального интервала (разрыва) между элементами в идеально распределенном массиве.

Вычислите размер ведра (bucket size), необходимый для размещения всех элементов массива так, чтобы если массив был равномерно распределен, каждый ведер должен содержать хотя бы один элемент. Размер ведра = (max_value - min_value) / (количество элементов - 1).

2️⃣

Размещение элементов в ведрах:

Создайте ведра для хранения минимальных и максимальных значений каждого ведра. Используйте формулу для распределения каждого элемента в соответствующем ведре на основе его значения.

Игнорируйте пустые ведра при расчете максимального интервала.

3️⃣

Вычисление максимального интервала:

Пройдите через ведра и вычислите максимальный интервал, сравнивая минимальное значение текущего непустого ведра с максимальным значением предыдущего непустого ведра.

Максимальный интервал будет наибольшей разницей между "минимальными" и "максимальными" значениями последовательных непустых ведер.

😎