Last Updated: 2 Oct, 2021
Maximum Difference
Hard
Asked in companies
You are given an integer array ‘arr’ of size ‘N’. Your task is to find the maximum difference between two consecutive elements in the sorted form of the array ‘arr’.
If the ‘arr’ contains less than two elements, return 0.
For example:
You are given arr = {1, 3, 8, 6, 7}, then our answer will be 3.
Sorted form of arr = {1, 3, 6, 7, 8}. The maximum absolute difference between two consecutive elements is 6 - 3 = 3, which is the correct answer.
Input Format:
The first line contains an integer 'T' which denotes the number of test cases.
The first line of each test case contains an integer denoting the size of the ‘arr’.
The second contains ‘N’ space-separated integers representing the elements of the array ‘arr’.
Output Format:
For each test case, print a single integer, denoting the maximum difference between two consecutive elements in the sorted form of ‘arr’.
The output of each test case will be printed in a separate line.
Constraints:
1 <= T <= 10
1 <= N <= 10 ^ 6
0 <= arr[i] <= 10 ^ 9
Time limit: 1 sec
Note:
You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Approaches
In this approach, we will first sort the given array, find every consecutive pair of elements, and return the maximum difference. We will maintain a variable maxDiff to store the maximum difference.
Algorithm:
- Initialize a variable maxDiff with value 0.
- Sort the input array.
- Iterate i in 0 to n - 1
- maxDiff = maximum of maxDiff and (arr[i + 1] - arr[i])
- Finally, return maxDiff
This approach is similar the approach 1. The difference is that in this approach, we will use radix sort instead of comparison sort to sort the input array. Radix sort sorts the array by performing counting sort on individual digits starting from least significant digit to most significant digit.
Algorithm:
- If n is less than 2
- return 0
- Maintain a function radixSort(arr)
- Intialize a variable max with value arr[0]
- Iterate i in arr.length
- max = maximum of max and arr[i]
- Intialize a variable base with value 0
- Iterate exp = 1, while (max / exp) is greater than 0, exp *= base
- Maintain a function countSort(base, exp, arr)
- Intialize a variable n with value arr.length
- Intialize an integer array aux of size n
- Intialize an integer array count of size equal to base
- Iterate i in 0 to n
- count[(arr[i] / exp) % 10]++.
- Iterate i = n-1, while i is greater than 0, i--
- aux[--count[(arr[i] / exp) % 10]] = arr[i].
- Iterate i in 0 to n
- arr[i] = aux[i]
- Intialize a variable maxDiff with value MIN_VALUE
- Iterate i in 0 to n - 1
- maxDiff = maximum of maxDiff and arr[i + 1] - arr[i]
- Finally, return maxDiff
In this approach, we will divide elements into buckets. We will store minimum and maximum values for each bucket and compare them to find the final answer. Bucket Sort stores elements into buckets of some fixed size and then sorts each bucket, which takes less processing time as compared to comparison sorts.
Algorithm:
- Initialize a variable minimum with the maximum integer value.
- Initialize a variable maximum with the minimum integer value.
- Iterate i in 0 to arr.length
- minimum = minimum of minimum and arr[i]
- maximum = maximum of maximum and arr[i]
- If the minimum is equal to the maximum
- return 0
- Initialize a variable bucketSize with value ceil((maximum - minimum )/(arr.length - 1))
- Initialize an integer array minBuckets of size n.
- Initialize an integer array maxBuckets of size n.
- Set all values of minBuckets to the maximum integer value.
- Set all values of maxBuckets to the minimum integer value.
- Iterate i in 0 to n
- Initialize a variable bucketIndex with equal to (arr[i]-minimum)/bucketSize.
- minBuckets[bucketIndex] = minimum of minBuckets[bucketIndex] and arr[i]
- maxBuckets[bucketIndex] = maximum of maxBuckets[bucketIndex] and arr[i]
- Initialize a variable maxDiff with value 0;
- Iterate i in 0 to minBuckets.length
- If minBuckets[i] is not equal to the maximum integer value.
- maxDiff = maximum of maxDiff and (minBuckets[i] - minimum);
- minimum = maxBuckets[I].
- If minBuckets[i] is not equal to the maximum integer value.
- Finally, return maxDiff.