# Maximum of Absolute Value Expression **Difficulty:** MEDIUM [External](https://leetcode.com/problems/maximum-of-absolute-value-expression) Canonical: https://scaleengineer.com/dsa/problems/maximum-of-absolute-value-expression **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math) **Data structures:** Array --- ## Problem 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^6` # Approaches ## Brute Force Iteration This approach directly implements the problem statement by checking every possible pair of indices `(i, j)`. It uses nested loops to iterate through all combinations and calculates the value of the expression `|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|` for each pair. The maximum value found during this process is stored and returned as the result. **Time:** O(n^2), where n is the length of the arrays. The nested loops result in n*n iterations. · **Space:** O(1), as we only use a few variables to store the intermediate and final results, regardless of the input size. **Pros:** Simple to understand and implement.; Directly follows the problem definition. **Cons:** Inefficient for large inputs. With `n` up to 40000, this will lead to a "Time Limit Exceeded" error. ### Explanation The brute-force method is the most straightforward way to solve the problem. It considers every single pair of indices `(i, j)` and computes the expression's value. By keeping track of the largest value seen so far, we can find the overall maximum. While simple, its performance degrades quadratically with the size of the input arrays, making it unsuitable for the given constraints. ```java class Solution { public int maxAbsValExpr(int[] arr1, int[] arr2) { int n = arr1.length; int maxVal = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int val = Math.abs(arr1[i] - arr1[j]) + Math.abs(arr2[i] - arr2[j]) + Math.abs(i - j); if (val > maxVal) { maxVal = val; } } } return maxVal; } } ``` ### Algorithm - Initialize a variable `maxVal` to 0. - Get the length of the arrays, `n`. - Use a nested loop to iterate through all pairs of indices `(i, j)` from `0` to `n-1`. - For each pair `(i, j)`, calculate the value `currentVal = |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|`. - Update `maxVal = max(maxVal, currentVal)`. - After the loops complete, return `maxVal`. ## Mathematical Simplification (Manhattan Distance) This approach reformulates the problem to avoid the O(n^2) complexity. The expression `|a - b|` can be written as `max(a - b, b - a)`. By expanding the absolute value functions, we can identify four key expressions that need to be maximized. The original expression is the Manhattan distance between points `(arr1[i], arr2[i], i)` and `(arr1[j], arr2[j], j)`. This allows us to solve the problem in linear time. **Time:** O(n), where n is the length of the arrays. We perform a single pass through the arrays. · **Space:** O(1), as we only use a constant number of variables to store the min/max values. **Pros:** Highly efficient and optimal.; Handles large inputs within the time limits. **Cons:** The mathematical derivation is less intuitive than the brute-force approach. ### Explanation The expression is `|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|`. Each `|x - y|` term can be either `x - y` or `y - x`. This gives `2*2*2 = 8` combinations of signs. Let's analyze one such combination: `(arr1[i] - arr1[j]) + (arr2[i] - arr2[j]) + (i - j)`. We can regroup the terms by index `i` and `j`: `(arr1[i] + arr2[i] + i) - (arr1[j] + arr2[j] + j)`. To maximize this difference `A - B`, we need to find the maximum possible value for the `i`-th term and the minimum possible value for the `j`-th term over all possible indices. So, for this specific combination, the maximum value is `max(arr1[k] + arr2[k] + k) - min(arr1[k] + arr2[k] + k)` over all `k`. By analyzing all 8 sign combinations, we find that they come in pairs that produce the same result (e.g., `(+,+,+)` and `(-,-,-)`). This reduces the problem to finding the `max - min` for just four unique expressions. We can find the maximum and minimum values for each of these four expressions in a single pass through the arrays. The final answer is the maximum of the four `(max - min)` differences. ```java class Solution { public int maxAbsValExpr(int[] arr1, int[] arr2) { int n = arr1.length; int max1 = Integer.MIN_VALUE, min1 = Integer.MAX_VALUE; int max2 = Integer.MIN_VALUE, min2 = Integer.MAX_VALUE; int max3 = Integer.MIN_VALUE, min3 = Integer.MAX_VALUE; int max4 = Integer.MIN_VALUE, min4 = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { // Case 1: arr1[i] + arr2[i] + i int val1 = arr1[i] + arr2[i] + i; max1 = Math.max(max1, val1); min1 = Math.min(min1, val1); // Case 2: arr1[i] + arr2[i] - i int val2 = arr1[i] + arr2[i] - i; max2 = Math.max(max2, val2); min2 = Math.min(min2, val2); // Case 3: arr1[i] - arr2[i] + i int val3 = arr1[i] - arr2[i] + i; max3 = Math.max(max3, val3); min3 = Math.min(min3, val3); // Case 4: arr1[i] - arr2[i] - i int val4 = arr1[i] - arr2[i] - i; max4 = Math.max(max4, val4); min4 = Math.min(min4, val4); } int diff1 = max1 - min1; int diff2 = max2 - min2; int diff3 = max3 - min3; int diff4 = max4 - min4; return Math.max(Math.max(diff1, diff2), Math.max(diff3, diff4)); } } ``` ### Algorithm - Initialize eight variables to track the min and max of four key expressions: `max1, min1, max2, min2, max3, min3, max4, min4`. Initialize them with extreme values or with the values from the first element (index 0). - Iterate through the arrays from `i = 0` to `n-1`. - In each iteration, calculate the four transformed values: - `v1 = arr1[i] + arr2[i] + i` - `v2 = arr1[i] + arr2[i] - i` - `v3 = arr1[i] - arr2[i] + i` - `v4 = arr1[i] - arr2[i] - i` - Update the min/max for each of the four expressions (e.g., `max1 = max(max1, v1)`, `min1 = min(min1, v1)`). - After the loop, calculate the maximum difference for each of the four cases: `max1 - min1`, `max2 - min2`, `max3 - min3`, `max4 - min4`. - The result is the maximum of these four differences. # Solutions ### Java ```java class Solution { public int maxAbsValExpr(int[] arr1, int[] arr2) { int[] dirs = {1, -1, -1, 1, 1}; final int inf = 1 << 30; int ans = -inf; int n = arr1.length; for (int k = 0; k < 4; ++k) { int a = dirs[k], b = dirs[k + 1]; int mx = -inf, mi = inf; for (int i = 0; i < n; ++i) { mx = Math.max(mx, a * arr1[i] + b * arr2[i] + i); mi = Math.min(mi, a * arr1[i] + b * arr2[i] + i); ans = Math.max(ans, mx - mi); } } return ans; } } ``` ### CPP ```cpp class Solution { public: int maxAbsValExpr(vector &arr1, vector &arr2) { int dirs[5] = {1, -1, -1, 1, 1}; const int inf = 1 << 30; int ans = -inf; int n = arr1.size(); for (int k = 0; k < 4; ++k) { int a = dirs[k], b = dirs[k + 1]; int mx = -inf, mi = inf; for (int i = 0; i < n; ++i) { mx = max(mx, a * arr1[i] + b * arr2[i] + i); mi = min(mi, a * arr1[i] + b * arr2[i] + i); ans = max(ans, mx - mi); } } return ans; } }; ``` ### Python ```python class Solution: def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int: dirs = (1, - 1, - 1, 1, 1) ans = - inf for a, b in pairwise(dirs): mx, mi = - inf, inf for i, (x, y) in enumerate(zip(arr1, arr2)): mx = max(mx, a * x + b * y + i) mi = min(mi, a * x + b * y + i) ans = max(ans, mx - mi) return ans ```