Maximum Difference Between Adjacent Elements in a Circular Array

Maximum Difference Between Adjacent Elements in a Circular Array - Problem

Array Easy

Given a circular array nums, find the maximum absolute difference between adjacent elements.

Note: In a circular array, the first and last elements are adjacent.

For example, if nums = [1, 5, 3, 9], the adjacent pairs are: (1,5), (5,3), (3,9), and (9,1).

Input & Output

Example 1 — Basic Circular Array

$ Input: nums = [1, 5, 3, 9]

› Output: 8

💡 Note: Adjacent pairs are: (1,5)→4, (5,3)→2, (3,9)→6, (9,1)→8. Maximum difference is 8 between last and first elements.

Example 2 — Small Array

$ Input: nums = [2, 7]

› Output: 5

💡 Note: Only one adjacent pair: (2,7) and (7,2), both have difference |2-7| = 5.

Example 3 — All Same Elements

$ Input: nums = [5, 5, 5, 5]

› Output: 0

💡 Note: All adjacent differences are |5-5| = 0, so maximum is 0.

Constraints

2 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is remembering that in a circular array, the last element is adjacent to the first. The optimal approach is a single pass checking all adjacent pairs including the wraparound case. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Optimized	O(n)	O(1)	One pass with early termination opportunities
Brute Force	O(n)	O(1)	Check all adjacent pairs including wraparound

Single Pass Optimized — Algorithm Steps

Step 1: Find min and max values for theoretical maximum
Step 2: Iterate through adjacent pairs
Step 3: Early terminate if theoretical max is reached

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Min/Max

Calculate theoretical maximum difference

Check Pairs

Compare adjacent elements as before

Early Exit

Stop if we find the theoretical maximum

Code -

solution.c — C

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

int abs_diff(int a, int b) {
    return a > b ? a - b : b - a;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int* nums, int numsSize) {
    if (numsSize < 2) return 0;
    
    // Find theoretical maximum possible difference
    int minVal = nums[0], maxVal = nums[0];
    for (int i = 1; i < numsSize; i++) {
        minVal = min(minVal, nums[i]);
        maxVal = max(maxVal, nums[i]);
    }
    int theoreticalMax = maxVal - minVal;
    
    int maxDiff = 0;
    
    // Check all adjacent pairs including wraparound
    for (int i = 0; i < numsSize; i++) {
        int nextIndex = (i + 1) % numsSize;
        int diff = abs_diff(nums[i], nums[nextIndex]);
        maxDiff = max(maxDiff, diff);
        
        // Early termination if we found theoretical maximum
        if (maxDiff == theoreticalMax) {
            break;
        }
    }
    
    return maxDiff;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int numsSize = 0;
    char* ptr = line + 1; // Skip '['
    
    while (*ptr && *ptr != ']') {
        if (*ptr >= '0' && *ptr <= '9' || *ptr == '-') {
            nums[numsSize++] = atoi(ptr);
            while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
        }
        if (*ptr == ',') ptr++;
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Still need to check all pairs in worst case, but can terminate early sometimes

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

26.4K Views

Medium Frequency

~8 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass Optimized — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler