3423. Maximum Difference Between Adjacent Elements in a Circular Array

EasyArray

Leetcode Link

Problem Description

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve this problem, we need to understand the concept of a circular array, where the last element connects back to the first element. This requires us to consider the first and last element as adjacent in addition to all consecutive pairs of elements.

The key idea is to traverse the array nums and compute the absolute difference between each pair of consecutive elements. Keep track of the largest difference found during this traversal. We also compute the difference between the first and last elements separately, as they are adjacent in the circular array structure. The solution is the maximum value obtained from these comparisons.

By iterating through the entire array once and checking the wrapping pair separately, we can efficiently determine the maximum absolute difference between any two adjacent elements in the circular arrangement.

Solution Approach

The solution uses a straightforward simulation approach to solve the problem. Here's how it is done:

Iterate Through the Array: Traverse the array nums and calculate the absolute differences between each pair of consecutive elements. This is done using list comprehension with the pairwise function, which generates pairs of consecutive elements from the list:
```
max(abs(a - b) for a, b in pairwise(nums))
```
Circular Condition: Since the array is circular, compute the absolute difference between the first and last elements, treating them as an adjacent pair:
```
abs(nums[0] - nums[-1])
```

Find the Maximum Difference: Compare the maximum difference found from consecutive pairs with the difference between the first and last elements to find the overall maximum:

return max(max(abs(a - b) for a, b in pairwise(nums)), abs(nums[0] - nums[-1]))

This approach is efficient, as it computes the maximum difference in a single pass through the array, with the circular condition accounted for separately.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through this solution with a small example of a circular array. Consider the array nums = [4, 7, 1, 10].

Iterate Through the Array:
- Compute the absolute differences between consecutive elements:
  - Between 4 and 7: |4 - 7| = 3
  - Between 7 and 1: |7 - 1| = 6
  - Between 1 and 10: |1 - 10| = 9
Circular Condition:
- Since the array is circular, also compute the absolute difference between the first and last elements:
  - Between 10 and 4: |10 - 4| = 6
Find the Maximum Difference:
- From the differences calculated: 3, 6, 9, and the circular difference 6, the maximum absolute difference is 9.

Therefore, the maximum absolute difference between adjacent elements in this circular array is 9.

Solution Implementation

1from typing import List
2from itertools import pairwise
3
4class Solution:
5    def maxAdjacentDistance(self, nums: List[int]) -> int:
6        # Calculate the maximum absolute difference between adjacent elements
7        max_adjacent_diff = max(abs(a - b) for a, b in pairwise(nums))
8      
9        # Additionally, include the absolute difference between the first and last elements
10        circular_diff = abs(nums[0] - nums[-1])
11      
12        # Return the maximum of these differences
13        return max(max_adjacent_diff, circular_diff)
14

1class Solution {
2    public int maxAdjacentDistance(int[] nums) {
3        int n = nums.length;  // Get the length of the array
4        // Initialize 'ans' with the absolute difference between the first and last element
5        int ans = Math.abs(nums[0] - nums[n - 1]);
6      
7        // Iterate over the array starting from the second element
8        for (int i = 1; i < n; ++i) {
9            // Calculate the absolute difference of adjacent elements and update 'ans' if larger
10            ans = Math.max(ans, Math.abs(nums[i] - nums[i - 1]));
11        }
12      
13        // Return the maximum absolute difference found
14        return ans;
15    }
16}
17

1#include <vector>
2#include <algorithm> // For std::max
3#include <cmath>     // For std::abs
4
5class Solution {
6public:
7    int maxAdjacentDistance(std::vector<int>& nums) {
8        // Initialize `ans` with the absolute difference between the 
9        // first and the last elements of the vector.
10        int ans = std::abs(nums[0] - nums.back());
11
12        // Iterate through the vector starting from the second element.
13        for (int i = 1; i < nums.size(); ++i) {
14            // Calculate the absolute difference between consecutive elements
15            // and update `ans` if this difference is greater.
16            ans = std::max(ans, std::abs(nums[i] - nums[i - 1]));
17        }
18
19        // Return the maximum adjacent distance found.
20        return ans;
21    }
22};
23

1// Function to calculate the maximum distance between any two adjacent elements in an array
2function maxAdjacentDistance(nums: number[]): number {
3    // Get the length of the array
4    const n = nums.length;
5  
6    // Initialize the answer with the absolute difference between the first and last element
7    let ans = Math.abs(nums[0] - nums[n - 1]);
8  
9    // Loop through the array starting from the second element
10    for (let i = 1; i < n; ++i) {
11        // Calculate the absolute difference between the current element and the previous one
12        // Update the answer if this difference is larger than the current answer
13        ans = Math.max(ans, Math.abs(nums[i] - nums[i - 1]));
14    }
15  
16    // Return the largest absolute difference found
17    return ans;
18}
19

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the list nums. This is because the solution iterates through the list, computing the absolute difference for each pair of adjacent elements and comparing them, taking linear time in the worst case. The space complexity is O(1), as the solution uses only a fixed amount of extra space for variables, regardless of the input size.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Which of the following is a good use case for backtracking?

Combinatorial problems

Random number generation

Topological sorting

Matrix multiplication

I don't know