Maximum Difference Between Adjacent Elements in a Circular Array
EasyPrompt
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.
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 <= 100-100 <= nums[i] <= 100
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves two main steps. First, we iterate through the array to compute the absolute difference for every pair of adjacent elements, including the circular pair (last and first elements). These differences are stored in an auxiliary data structure, like a list. In the second step, we find the maximum value within this list of differences.
Algorithm
- Get the length of the array,
n. - Create a new list,
differences, to store the absolute differences. - Iterate from
i = 0ton - 2. In each iteration, calculatediff = Math.abs(nums[i+1] - nums[i])and add it to thedifferenceslist. - Calculate the difference for the circular pair:
circularDiff = Math.abs(nums[0] - nums[n-1]). Add this to thedifferenceslist. - Find the maximum value in the
differenceslist, for example, by usingCollections.max(). - Return the maximum value found.
Walkthrough
The core idea is to first collect all the results (the differences) and then process them. We traverse the array once to calculate the difference between nums[i] and nums[i+1] for all valid i, and also the difference between the last and first elements. Each of these differences is stored. After populating our list of differences, a second operation is performed to find the maximum value within that list. While straightforward, this method consumes extra memory to hold the intermediate results.
import java.util.ArrayList;import java.util.List;import java.util.Collections; class Solution { public int maxAdjacentDifference(int[] nums) { int n = nums.length; if (n < 2) { return 0; } List<Integer> differences = new ArrayList<>(); // Calculate differences for non-circular adjacent pairs for (int i = 0; i < n - 1; i++) { differences.add(Math.abs(nums[i + 1] - nums[i])); } // Calculate difference for the circular pair (last and first) differences.add(Math.abs(nums[0] - nums[n - 1])); // Find the maximum value in the list of differences return Collections.max(differences); }}Complexity
Time
O(n), where `n` is the number of elements in the array. We iterate through the array once to compute the differences (O(n)) and then find the maximum in the new list (O(n)).
Space
O(n), where `n` is the number of elements in the array. We use an auxiliary list to store `n` differences.
Trade-offs
Pros
Simple to understand and implement.
Clearly separates the logic of calculating differences from finding the maximum.
Cons
Uses extra space proportional to the input size, which is unnecessary for this problem.
Less efficient in terms of memory compared to a single-pass solution.
Solutions
Solution
public class Solution { public int MaxAdjacentDistance ( int [] nums ) { int n = nums . Length ; int ans = Math . Abs ( nums [ 0 ] - nums [ n - 1 ]); for ( int i = 1 ; i < n ; ++ i ) { ans = Math . Max ( ans , Math . Abs ( nums [ i ] - nums [ i - 1 ])); } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.