LeetCode Problem 3423

Difficulty: 🟢 Easy
Topics: Array

Solution

LeetCode 3423 - Maximum Difference Between Adjacent Elements in a Circular Array

Problem Understanding

This problem gives us an integer array nums and asks us to find the largest absolute difference between any two adjacent elements.

The important detail is that the array is circular. In a normal array, element i is adjacent only to elements i - 1 and i + 1 when those indices exist. In a circular array, the first and last elements are also considered adjacent. Therefore, we must evaluate:

• |nums[0] - nums[1]|
• |nums[1] - nums[2]|
• ...
• |nums[n-2] - nums[n-1]|
• |nums[n-1] - nums[0]|

The answer is the maximum value among all of these absolute differences.

The input consists of:

• An integer array nums
• Length between 2 and 100
• Values between -100 and 100

The output is a single integer representing the maximum absolute difference between adjacent elements in the circular arrangement.

The constraints are very small. With at most 100 elements, even simple approaches are easily fast enough. However, we should still identify the most direct and efficient solution.

Several edge cases are worth noting:

• Arrays with only two elements. Since the array is circular, the same pair appears twice, but the maximum difference is still simply their absolute difference.
• Arrays containing negative numbers. We must use absolute values correctly.
• Arrays where the largest difference occurs between the last and first elements rather than between consecutive indices inside the array.
• Arrays where all values are identical, producing an answer of 0.

Problem Understanding

The problem gives us a circular integer array nums and asks us to compute the maximum absolute difference between any two adjacent elements.

In a normal array, adjacent elements are pairs like:

• nums[i] and nums[i + 1]

However, this problem introduces an important twist: the array is circular. That means the first and last elements are also considered adjacent. So for an array of length n, we must also evaluate:

• nums[n - 1] and nums[0]

The goal is to return the largest value among all absolute differences between adjacent pairs.

For example, if:

nums = [1, 2, 4]

the adjacent pairs are:

• (1, 2) → difference 1
• (2, 4) → difference 2
• (4, 1) → difference 3 because the array is circular

The answer is therefore 3.

The constraints are very small:

• 2 <= nums.length <= 100
• -100 <= nums[i] <= 100

These limits tell us several important things:

• The input size is tiny, so even less efficient solutions would still run comfortably within limits.
• Integer overflow is not a concern.
• We do not need advanced optimizations or data structures.

Still, the problem is fundamentally about scanning adjacent pairs efficiently and correctly handling the circular relationship.

The most important edge case is remembering that the last and first elements are adjacent. A common bug is to only compare consecutive elements inside the array and forget the wraparound comparison.

Another edge case involves arrays of length 2. In that case, the two elements are adjacent in both directions, but the absolute difference is the same either way. The algorithm should still work naturally without any special handling.

Negative numbers are also important because the problem asks for absolute differences. A naive subtraction without abs() would produce incorrect results.

Approaches

Brute Force Approach

The most straightforward solution is to explicitly examine every adjacent pair in the circular array.

For each index i, we determine its next neighbor using:

nextIndex = (i + 1) % n

This modulo operation naturally wraps the last index back to index 0, handling the circular property.

For every pair (nums[i], nums[nextIndex]), we compute:

abs(nums[i] - nums[nextIndex])

and keep track of the largest value encountered.

This approach checks every adjacent pair exactly once, so it always produces the correct answer.

Because there are only n adjacent pairs, the running time is already linear.

Optimal Approach

There is actually no more efficient asymptotic solution than examining all adjacent pairs.

The key observation is that the answer depends solely on the differences between neighboring elements. Since every adjacent relationship could potentially contain the maximum difference, we must inspect each one at least once.

Therefore, a single linear scan of the array is both necessary and sufficient.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Checks every circular adjacent pair directly
Optimal	O(n)	O(1)	Single pass over all adjacent pairs, asymptotically optimal

Algorithm Walkthrough

Optimal Algorithm

1. Let n be the length of nums.
2. Initialize a variable max_difference to 0.
3. Iterate through every index i from 0 to n - 1.
4. Compute the index of the adjacent element:

next_index = (i + 1) % n

The modulo operation ensures that when i is the last index, the next index becomes 0, correctly implementing the circular behavior. 5. Compute the absolute difference:

difference = abs(nums[i] - nums[next_index])

6. Update the running maximum:

max_difference = max(max_difference, difference)

7. After all indices have been processed, return max_difference.

Why it works

Every adjacent pair in a circular array is exactly represented by (i, (i + 1) % n) for some index i. The algorithm evaluates the absolute difference for each such pair and stores the largest value encountered. Since the maximum must be among these examined pairs, the final result is guaranteed to be the correct answer. The brute-force idea is straightforward. We examine every adjacent pair in the circular array and compute its absolute difference. We keep track of the maximum difference seen so far.

Since the array is circular, each index i is adjacent to:

(i + 1) % n

Using modulo automatically wraps the final element back to index 0.

This approach is correct because it explicitly evaluates every valid adjacent pair exactly once and selects the largest difference.

Although this solution is called "brute force", it is already efficient because the problem itself is simple. There is no hidden optimization beyond scanning all adjacent pairs once.

Key Insight

The key observation is that every valid answer must come from one of the n adjacent pairs in the circular array.

There is no need for nested loops, sorting, or additional data structures because the problem only concerns local neighboring relationships.

Once we realize that each element only needs to be compared with its next circular neighbor, the solution becomes a single linear scan.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Checks every adjacent circular pair directly
Optimal	O(n)	O(1)	Same linear scan, this is already optimal

Algorithm Walkthrough

1. Store the length of the array in a variable n.

This helps us repeatedly access the size during iteration and simplifies modulo calculations. 2. Initialize a variable called max_difference to 0.

This variable will store the largest absolute difference found so far. 3. Iterate through every index i from 0 to n - 1.

Each index represents the first element in an adjacent pair. 4. Compute the index of the next adjacent element using:

(i + 1) % n

The modulo operation is critical because it wraps the last index back to 0, which correctly models the circular array behavior. 5. Compute the absolute difference between the current element and the next element.

Use:

abs(nums[i] - nums[next_index])

The absolute value ensures negative differences are handled correctly. 6. Update max_difference if the current difference is larger.

This guarantees we always retain the best answer seen so far. 7. After the loop finishes, return max_difference.

Why it works

The algorithm works because every adjacent pair in a circular array can be represented as:

(nums[i], nums[(i + 1) % n])

for every valid index i.

The loop evaluates all such pairs exactly once, computes their absolute differences, and keeps the maximum value. Since the answer must come from one of these pairs, the algorithm is guaranteed to return the correct result.

Python Solution

from typing import List

class Solution:
    def maxAdjacentDistance(self, nums: List[int]) -> int:
        n = len(nums)
        max_difference = 0

        for i in range(n):
            next_index = (i + 1) % n
            difference = abs(nums[i] - nums[next_index])
            max_difference = max(max_difference, difference)
            current_difference = abs(nums[i] - nums[next_index])

            max_difference = max(max_difference, current_difference)

        return max_difference

The implementation begins by storing the array length in n. A variable named max_difference keeps track of the largest absolute difference found so far.

The loop visits every index in the array. For each index, (i + 1) % n identifies the adjacent element in the circular structure. This automatically wraps the final element back to the first element.

The absolute difference between the current element and its neighbor is computed and compared against the current maximum. After processing all adjacent pairs, the stored maximum is returned.

The implementation directly mirrors the algorithm described above and uses only constant extra space. The implementation follows the algorithm directly.

First, we store the array length in n. This allows us to compute circular neighbors efficiently using modulo arithmetic.

The variable max_difference tracks the largest difference encountered during iteration.

The loop visits every index exactly once. For each position, the next adjacent index is calculated using:

(i + 1) % n

This is the most important detail in the solution because it correctly handles the circular relationship between the last and first elements.

We then compute the absolute difference between the two adjacent elements and update the running maximum.

After all adjacent pairs have been processed, the function returns the final maximum difference.

Go Solution

package main

import "math"

func maxAdjacentDistance(nums []int) int {
    n := len(nums)
    maxDifference := 0

    for i := 0; i < n; i++ {
        nextIndex := (i + 1) % n

        difference := nums[i] - nums[nextIndex]
        if difference < 0 {
            difference = -difference
        }

        if difference > maxDifference {
            maxDifference = difference
        currentDifference := int(math.Abs(float64(nums[i] - nums[nextIndex])))

        if currentDifference > maxDifference {
            maxDifference = currentDifference
        }
    }

    return maxDifference
}

The Go implementation follows exactly the same logic as the Python version. Since Go does not provide a built in integer abs function, the absolute value is computed manually by negating negative differences. No special handling for integer overflow is required because the constraints are very small, with values only between -100 and 100. The Go implementation is structurally identical to the Python solution.

One Go-specific detail is the use of math.Abs, which operates on float64 values. Because of this, the integer difference must first be converted to float64, and the result must then be converted back to int.

The constraints are very small, so integer overflow is not a concern.

Go slices naturally provide the array behavior needed for iteration, and modulo arithmetic handles the circular adjacency exactly the same way as in Python.

Worked Examples

Example 1

Input:

nums = [1, 2, 4]

Adjacent pairs in the circular array are:

(1, 2)
(2, 4)
(4, 1)

i	nums[i]	Neighbor	Difference	max_difference
0	1	2	1	1
1	2	4	2	2
2	4	1	3	3
We evaluate every adjacent circular pair.

i	nums[i]	next_index	nums[next_index]	abs difference	max_difference
0	1	1	2	1	1
1	2	2	4	2	2
2	4	0	1	3	3

Final answer:

3

Example 2

Input:

nums = [-5, -10, -5]

Adjacent pairs:

(-5, -10)
(-10, -5)
(-5, -5)

i	nums[i]	Neighbor	Difference	max_difference
0	-5	-10	5	5
1	-10	-5	5	5
2	-5	-5	0	5
i	nums[i]	next_index	nums[next_index]	abs difference
---	---	---	---	---
0	-5	1	-10	5
1	-10	2	-5	5
2	-5	0	-5	0

Final answer:

5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each adjacent pair is examined exactly once
Space	O(1)	Only a few variables are used regardless of input size

The algorithm performs a single pass through the array. Since there are n elements and each iteration does constant work, the running time is O(n). The memory usage remains constant because no auxiliary data structures are created.

Test Cases

sol = Solution()

assert sol.maxAdjacentDistance([1, 2, 4]) == 3  # provided example 1
assert sol.maxAdjacentDistance([-5, -10, -5]) == 5  # provided example 2

assert sol.maxAdjacentDistance([1, 10]) == 9  # minimum length array
assert sol.maxAdjacentDistance([5, 5]) == 0  # two equal elements

assert sol.maxAdjacentDistance([7, 7, 7, 7]) == 0  # all identical values

assert sol.maxAdjacentDistance([1, 2, 10]) == 9  # maximum from circular pair
assert sol.maxAdjacentDistance([10, 1, 2]) == 9  # circular difference again

assert sol.maxAdjacentDistance([-100, 100]) == 200  # extreme values

assert sol.maxAdjacentDistance([-1, -4, -8]) == 7  # all negative values

assert sol.maxAdjacentDistance([3, -2, 5, -7]) == 12  # mixed positive and negative

assert sol.maxAdjacentDistance([0, 1, 2, 3, 100]) == 100  # last-first pair is largest

assert sol.maxAdjacentDistance([100, 0, 100, 0]) == 100  # repeated maximum differences

Test Summary

Test	Why
[1, 2, 4]	Verifies the first example
[-5, -10, -5]	Verifies the second example
[1, 10]	Minimum valid array size
[5, 5]	Minimum size with zero difference
[7, 7, 7, 7]	All values equal
[1, 2, 10]	Largest difference comes from circular connection
[10, 1, 2]	Another circular boundary case
[-100, 100]	Maximum possible absolute difference
[-1, -4, -8]	Negative numbers only
[3, -2, 5, -7]	Mixed positive and negative values
[0, 1, 2, 3, 100]	Large boundary difference
[100, 0, 100, 0]	Multiple pairs share the maximum

Edge Cases

Arrays of Length Two

When the array contains exactly two elements, the circular adjacency causes the same pair to appear in both directions. A common mistake is to overcomplicate this situation. The implementation simply evaluates both circular pairs, producing the correct maximum absolute difference automatically.

Maximum Difference at the Circular Boundary

Many bugs occur when developers only compare consecutive indices and forget that the last and first elements are also adjacent. For example, in [1, 2, 10], the largest difference is |10 - 1| = 9. Using (i + 1) % n guarantees that this boundary pair is always included.

Negative Values

When negative numbers are present, subtracting values directly can produce negative results. The problem asks for the absolute difference, not the signed difference. The implementation always applies abs() in Python and explicit absolute value logic in Go, ensuring correct handling of cases such as [-100, 100].

All Elements Equal

If every element has the same value, every adjacent difference is 0. Some implementations incorrectly initialize the answer with a nonzero value. By initializing max_difference to 0 and only updating it when a larger difference is found, the algorithm correctly returns 0.

Multiple Maximum Pairs

Several adjacent pairs may share the same maximum difference. Since the problem only asks for the value of the maximum difference, not the pair that achieves it, the implementation simply tracks the largest value seen so far. Duplicate occurrences do not affect correctness. | Time | O(n) | Each element is processed exactly once | | Space | O(1) | Only a few variables are used |

The algorithm performs a single pass through the array, so the running time grows linearly with the number of elements.

No additional data structures proportional to input size are allocated, so the space usage remains constant.

Test Cases

from typing import List

class Solution:
    def maxAdjacentDistance(self, nums: List[int]) -> int:
        n = len(nums)
        max_difference = 0

        for i in range(n):
            next_index = (i + 1) % n
            current_difference = abs(nums[i] - nums[next_index])

            max_difference = max(max_difference, current_difference)

        return max_difference

solution = Solution()

assert solution.maxAdjacentDistance([1, 2, 4]) == 3
# Tests circular adjacency between last and first

assert solution.maxAdjacentDistance([-5, -10, -5]) == 5
# Tests negative numbers

assert solution.maxAdjacentDistance([7, 7]) == 0
# Tests minimum array size with equal values

assert solution.maxAdjacentDistance([1, 100]) == 99
# Tests minimum array size with large difference

assert solution.maxAdjacentDistance([0, 0, 0, 0]) == 0
# Tests all identical elements

assert solution.maxAdjacentDistance([1, 3, 6, 10]) == 9
# Maximum comes from circular pair (10,1)

assert solution.maxAdjacentDistance([-100, 100]) == 200
# Tests largest possible absolute difference

assert solution.maxAdjacentDistance([5, -5, 5, -5]) == 10
# Tests alternating positive and negative values

assert solution.maxAdjacentDistance([2, 4, 6, 8, 10]) == 8
# Circular comparison larger than internal comparisons

assert solution.maxAdjacentDistance([9, 1, 8, 2]) == 8
# Multiple candidate differences

Test Summary

Test	Why
[1, 2, 4]	Validates circular adjacency handling
[-5, -10, -5]	Validates negative number handling
[7, 7]	Tests smallest valid size with zero difference
[1, 100]	Tests smallest valid size with large difference
[0, 0, 0, 0]	Ensures identical values work correctly
[1, 3, 6, 10]	Ensures wraparound pair is checked
[-100, 100]	Tests maximum constraint range
[5, -5, 5, -5]	Tests alternating sign values
[2, 4, 6, 8, 10]	Verifies circular comparison can dominate
[9, 1, 8, 2]	Tests multiple large candidate differences

Edge Cases

One important edge case is arrays of length two. Since the array is circular, both elements are adjacent to each other in both directions. A buggy implementation might accidentally double count or mishandle this situation. The current solution works naturally because it simply evaluates each circular neighbor relationship once per index.

Another critical edge case is forgetting the circular comparison between the last and first elements. Many implementations only compare nums[i] with nums[i + 1] for indices inside the array bounds. That would miss cases like [1, 2, 4], where the maximum difference comes from the pair (4, 1). Using modulo arithmetic guarantees the wraparound pair is always included.

Negative values are also a common source of mistakes. If the implementation subtracts values without taking the absolute value, negative results could incorrectly reduce the maximum difference. By using abs(nums[i] - nums[next_index]), the algorithm correctly measures distance regardless of sign.

A final edge case involves arrays where all values are identical. In such cases, every adjacent difference is 0. The implementation handles this correctly because max_difference starts at 0 and never increases.