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.
This is the most efficient approach. We can find the maximum difference in a single pass through the array without needing any extra storage. We maintain a variable to keep track of the maximum difference found so far and update it as we iterate through all adjacent pairs, including the circular one.
Algorithm
- Get the length of the array,
n. - Initialize a variable
maxDiffto 0. - Iterate from
i = 0ton - 1. - In each iteration, determine the next index in a circular manner:
nextIndex = (i + 1) % n. - Calculate the absolute difference between the current element and the next element:
currentDiff = Math.abs(nums[nextIndex] - nums[i]). - Update
maxDiffifcurrentDiffis larger:maxDiff = Math.max(maxDiff, currentDiff). - After the loop, return
maxDiff.
Walkthrough
By using a single loop and a single variable to track the maximum difference, we can solve the problem in one pass. The key to handling the circular nature elegantly is the modulo operator (%). For an index i, the next index is (i + 1) % n. This works for all elements: for i = 0, (0 + 1) % n is 1; for i = n-2, (n-2 + 1) % n is n-1; and crucially, for the last element i = n-1, (n-1 + 1) % n is n % n, which is 0, correctly wrapping around to the first element. This way, all adjacent pairs are checked within a single, concise loop.
class Solution { public int maxAdjacentDifference(int[] nums) { int n = nums.length; int maxDiff = 0; for (int i = 0; i < n; i++) { // Use modulo operator to handle circularity int nextIndex = (i + 1) % n; int currentDiff = Math.abs(nums[nextIndex] - nums[i]); maxDiff = Math.max(maxDiff, currentDiff); } return maxDiff; }}Complexity
Time
O(n), where `n` is the number of elements. We iterate through the array exactly once.
Space
O(1), as we only use a constant amount of extra space for variables, regardless of the input size.
Trade-offs
Pros
Optimal time complexity, as it requires only a single pass.
Optimal space complexity, using only a constant amount of extra memory.
The code is concise and easy to read, especially with the modulo operator.
Cons
There are no significant cons for this approach as it is optimal for this problem.
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 ; } }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; }}class Solution {public: int maxAdjacentDistance(vector<int> &nums) { int ans = abs(nums[0] - nums.back()); for (int i = 1; i < nums.size(); ++i) { ans = max(ans, abs(nums[i] - nums[i - 1])); } return ans; }};class Solution: def maxAdjacentDistance(self, nums: List[int]) -> int: return max( max(abs(a - b) for a, b in pairwise(nums)), abs(nums[0] - nums[- 1]))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.