Given two arrays of integers with equal lengths, return the maximum value of:
|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|
where the maximum is taken over all 0 <= i, j < arr1.length.
Example 1:
Input: arr1 = [1,2,3,4], arr2 = [-1,4,5,6] Output: 13
Example 2:
Input: arr1 = [1,-2,-5,0,10], arr2 = [0,-2,-1,-7,-4] Output: 20
Constraints:
2 <= arr1.length == arr2.length <= 40000-10^6 <= arr1[i], arr2[i] <= 10^6The goal in #1131 Maximum of Absolute Value Expression is to maximize the value of |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|. A direct brute-force comparison of all pairs (i, j) would take O(n^2) time, which is inefficient for large inputs.
A key observation is that absolute values can be expanded into different sign combinations. By reorganizing the expression, it can be transformed into a small set of linear forms such as arr1[i] + arr2[i] + i and other sign variations. This reduces the problem to tracking the maximum and minimum values of these expressions while scanning the arrays.
For each transformation, compute the difference between the current maximum and minimum values to determine the best candidate result. Since only a constant number of expressions are evaluated, the algorithm processes the arrays in a single pass.
This optimized mathematical observation leads to a solution with O(n) time complexity and O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sign transformation with max/min tracking | O(n) | O(1) |
The Organic Chemistry Tutor
Use these hints if you're stuck. Try solving on your own first.
Use the idea that abs(A) + abs(B) = max(A+B, A-B, -A+B, -A-B).
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem appear in technical interviews because it tests mathematical insight, array traversal, and the ability to simplify absolute value expressions into efficient computations.
Absolute value expressions can be expanded into multiple cases depending on sign combinations. When applied to this formula, the expression reduces to a small set of linear transformations that allow efficient max–min comparisons instead of checking every pair.
The optimal approach rewrites the absolute value expression into several linear forms by considering sign combinations. By tracking the maximum and minimum values for each form while iterating through the arrays, the result can be computed in O(n) time.
The optimized solution does not require complex data structures. It only uses variables to track running maximum and minimum values for each transformed expression, making it space-efficient.