Maximum Difference Between Adjacent Elements in a Circular Array
Maximum Difference Between Adjacent Elements in a Circular Array solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Difference Between Adjacent Elements in a Circular Array is an easy coding problem on arrays, asked in TCS, Accenture and Capgemini interviews.
- Difficulty: Easy
- Topics: Arrays
- Asked at: TCS, Accenture, Capgemini
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The array nums is circular: the element after the last one is the first one again.
Return the maximum absolute difference between any two adjacent elements.
Example 1
Input: nums = [1,2,4]
Output: 3
Explanation: The wrap-around pair (4, 1) differs by 3, more than any straight neighbour.
Example 2
Input: nums = [-5,-10,-5]
Output: 5
Explanation: |-5 - (-10)| = 5.
Example 3
Input: nums = [7]
Output: 0
Explanation: A single element is its own neighbour.
Constraints
1 <= nums.length <= 100-100 <= nums[i] <= 100
Hints for Maximum Difference Between Adjacent Elements in a Circular Array
Hint 1
Every index
ipairs withi + 1, and the last index pairs with0.Hint 2
Modulo arithmetic —
(i + 1) % n— handles the wrap without a special case.Hint 3
A single-element array pairs with itself, so the answer is 0.
How to solve Maximum Difference Between Adjacent Elements in a Circular Array
The circular neighbour of index i is (i + 1) % n, so one loop over every index covers all n adjacent pairs, wrap included.
Approach
- Start
bestat0. - For each
i, compute|nums[i] - nums[(i + 1) % n]|. - Keep the largest value seen.
Why it works
In a circle of n elements there are exactly n adjacent pairs, one per starting index, and (i + 1) % n enumerates each exactly once.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Looping only to
n - 2misses the wrap-around pair, which is often the answer. - Forgetting the absolute value reports a negative difference as small.
Reference solution
Python
from typing import List
def maxAdjacentDistance(nums: List[int]) -> int:
n = len(nums)
return max(abs(nums[i] - nums[(i + 1) % n]) for i in range(n))Java
public static int maxAdjacentDistance(int[] nums) {
int n = nums.length, best = 0;
for (int i = 0; i < n; i++) {
int d = Math.abs(nums[i] - nums[(i + 1) % n]);
if (d > best) best = d;
}
return best;
}C++
int maxAdjacentDistance(vector<int>& nums) {
int n = (int) nums.size(), best = 0;
for (int i = 0; i < n; i++) {
int d = abs(nums[i] - nums[(i + 1) % n]);
if (d > best) best = d;
}
return best;
}JavaScript
var maxAdjacentDistance = function(nums) {
var n = nums.length, best = 0;
for (var i = 0; i < n; i++) {
var d = Math.abs(nums[i] - nums[(i + 1) % n]);
if (d > best) best = d;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays