Problem

Submissions

Hints & solutions

Discuss

Maximum Difference

Hard

0/120

Average time to solve is 40m

Contributed by

2 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

Sample Output 1:

 3
 4

Explanation:

For the first test case, 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.

For the second test case, you are given arr = {0, 6, 4, 8, 9}. Then our answer will be 4. 
Sorted form of arr = {0, 4, 6, 8, 9}. The maximum absolute difference between two consecutive elements is 4 - 0 = 4, which is the correct answer.

Sample Input 2:

Sample Output 2:

1
5

Hint 1

Hint 2

Hint 3

Sort the given array.

Approaches (3)

Approach 1

Approach 2

Approach 3

Comparison Sort

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

Time Complexity

O(N * log(N)), where N is the size of the input array.

The sorting of the array takes N * log(N) time in the worst case. Hence, the overall time complexity is O(N * log(N)).

Space Complexity

O(N). where N is the size of the input array.

The sorting of the array takes O(N) space in the worst case. Hence, the overall space complexity is O(N).

(100% EXP penalty)

Maximum Difference

Console