Watch 6 video solutions for Maximum of Absolute Value Expression, a medium level problem involving Array, Math. This walkthrough by Programming Live with Larry has 1,582 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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^6Problem Overview: Given two integer arrays arr1 and arr2, compute the maximum value of |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j| for any pair of indices i and j. The challenge is handling multiple absolute values efficiently without checking every pair.
Approach 1: Separate Absolute Values into Multiple Cases (O(n), O(1))
The expression contains three absolute values. Expanding them leads to several sign combinations. Instead of evaluating all O(n^2) pairs, rewrite the expression using four equivalent forms: arr1[i] + arr2[i] + i, arr1[i] + arr2[i] - i, arr1[i] - arr2[i] + i, and arr1[i] - arr2[i] - i. For each form, track the maximum and minimum value while iterating through the array once. The difference between the max and min gives the best candidate for that case. This reduces the search to four linear scans over the arrays, producing an overall time complexity of O(n) and constant extra space O(1). The approach relies purely on arithmetic transformation and simple iteration over the array.
Approach 2: Optimizing with Mathematical Factorization (O(n), O(1))
The expression can also be viewed as a Manhattan distance in a transformed coordinate space. By factoring the terms, the formula becomes (±arr1[i] ± arr2[i] ± i) - (±arr1[j] ± arr2[j] ± j). Only four sign configurations are required to cover every possible combination produced by the absolute values. For each configuration, compute a transformed value and maintain running minimum and maximum values during a single pass through the array. The maximum difference across all configurations gives the answer. This version is essentially the same optimization expressed more cleanly using mathematical reasoning and linear scans. Time complexity stays O(n) with O(1) auxiliary space.
Recommended for interviews: Interviewers expect the mathematical transformation that reduces the brute-force O(n^2) pair comparison into four linear passes. Showing the case expansion demonstrates understanding of absolute value properties, while implementing the factorized form highlights strong problem‑solving skills with array traversal and algebraic simplification.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Separate Absolute Values into Multiple Cases | O(n) | O(1) | Best general solution. Expands absolute values into four expressions and scans arrays once. |
| Mathematical Factorization | O(n) | O(1) | Preferred interview explanation. Uses algebraic transformation and Manhattan distance insight. |