Maximum Difference – Subsequent Integers

Find the maximum absolute difference between adjacent integers after sorting an array of N integers.

Understand the Problem

Problem Statement

Given N integers, sort them in ascending order and calculate the absolute difference between each pair of adjacent (subsequent) integers. The task is to find and print the maximum of these differences.

Constraints

2 ≤ N ≤ 100
1 ≤ Each integer value ≤ 10^5

Examples

Example 1

Input

6
5 9 3 6 4 8

Output

Explanation

After sorting: [3, 4, 5, 6, 8, 9]. Differences: 4-3=1, 5-4=1, 6-5=1, 8-6=2, 9-8=1. Maximum difference is 2.

Example 2

Input

7
88 12 49 10 49 63 53

Output

Explanation

After sorting: [10, 12, 49, 49, 53, 63, 88]. Differences: 12-10=2, 49-12=37, 49-49=0, 53-49=4, 63-53=10, 88-63=25. Maximum difference is 37.

Solution

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int n;
    scanf("%d", &n);
    
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    qsort(arr, n, sizeof(int), compare);
    
    int max_diff = 0;
    for (int i = 1; i < n; i++) {
        int diff = arr[i] - arr[i-1];
        if (diff > max_diff) {
            max_diff = diff;
        }
    }
    
    printf("%d\n", max_diff);
    return 0;
}

Time:O(N log N) - due to sorting

Space:O(1) - sorting in-place, only using constant extra space

Approach:

1. The program reads N and the array elements using scanf.
2. Uses qsort() with a custom comparator to sort the array in ascending order.
3. Iterates through the sorted array starting from index 1.
4. Calculates the difference between current element and previous element (no abs() needed since array is sorted).
5. Updates max_diff if current difference is larger.
6. Prints the maximum difference.

Visual Explanation

Loading diagram...

All Problems