Difficulty: Easy | Acceptance: 75.70% | Paid: No Topics: Array
You are given a circular array of integers. A circular array means that the end of the array connects to the beginning of the array. Your task is to find the maximum absolute difference between any two adjacent elements in the array.
Return the maximum absolute difference between adjacent elements.
- Examples
- Constraints
- Single Pass with Modulo
- Two Pass Approach
- Using Iterator Helpers
Examples
Example 1
Input:
nums = [1,2,4]
Output:
3
Explanation: Because nums is circular, nums[0] and nums[2] are adjacent. They have the maximum absolute difference of |4 - 1| = 3.
Example 2
Input:
nums = [-5,-10,-5]
Output:
5
Explanation: The adjacent elements nums[0] and nums[1] have the maximum absolute difference of |-5 - (-10)| = 5.
Constraints
2 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
Single Pass with Modulo
Intuition Iterate through the array once, using modulo operation to handle the circular nature by wrapping around to the first element when reaching the end.
Steps
- Initialize maxDiff to 0
- Iterate through each index from 0 to n-1
- Calculate absolute difference between current element and next element (using modulo for circular access)
- Update maxDiff if current difference is larger
- Return maxDiff
from typing import List
class Solution:
def maxDifference(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return 0
max_diff = 0
for i in range(n):
diff = abs(nums[i] - nums[(i + 1) % n])
max_diff = max(max_diff, diff)
return max_diff
Complexity
- Time: O(n)
- Space: O(1)
- Notes: Single pass with constant extra space, optimal solution
Two Pass Approach
Intuition Separate the circular pair handling from the linear pairs by doing two passes - one for consecutive elements and one for the wrap-around pair.
Steps
- Initialize maxDiff to 0
- First pass: iterate through indices 0 to n-2, comparing each element with its next neighbor
- Second pass: handle the circular pair by comparing last element with first element
- Return maxDiff
from typing import List
class Solution:
def maxDifference(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return 0
max_diff = 0
# First pass: linear adjacent pairs
for i in range(n - 1):
diff = abs(nums[i] - nums[i + 1])
max_diff = max(max_diff, diff)
# Second pass: circular pair (last and first)
diff = abs(nums[n - 1] - nums[0])
max_diff = max(max_diff, diff)
return max_diff
Complexity
- Time: O(n)
- Space: O(1)
- Notes: Same complexity as single pass, but avoids modulo operation
Using Iterator Helpers
Intuition Leverage language-specific iterator helpers and functional programming constructs to compute differences in a more declarative style.
Steps
- Create a rotated version of the array (first element moved to end)
- Zip the original array with the rotated array
- Map each pair to its absolute difference
- Find the maximum of all differences
from typing import List
class Solution:
def maxDifference(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return 0
# Create rotated array and compute differences
rotated = nums[1:] + [nums[0]]
return max(abs(a - b) for a, b in zip(nums, rotated))
Complexity
- Time: O(n)
- Space: O(n) for rotated array in Python/JS/TS, O(1) for Java/C++
- Notes: More readable but may use extra space depending on implementation