Maximum of Absolute Value Expression
MedPrompt
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: 13Example 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
2 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize a variable
maxValto 0. - Get the length of the arrays,
n. - Use a nested loop to iterate through all pairs of indices
(i, j)from0ton-1. - For each pair
(i, j), calculate the valuecurrentVal = |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|. - Update
maxVal = max(maxVal, currentVal). - After the loops complete, return
maxVal.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
Pros
Simple to understand and implement.
Directly follows the problem definition.
Cons
Inefficient for large inputs. With
nup to 40000, this will lead to a "Time Limit Exceeded" error.
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.
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 = 0ton-1. - In each iteration, calculate the four transformed values:
v1 = arr1[i] + arr2[i] + iv2 = arr1[i] + arr2[i] - iv3 = arr1[i] - arr2[i] + iv4 = 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.
Walkthrough
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.
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)); }}Complexity
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.
Trade-offs
Pros
Highly efficient and optimal.
Handles large inputs within the time limits.
Cons
The mathematical derivation is less intuitive than the brute-force approach.
Solutions
Solution
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; }}class Solution {public: int maxAbsValExpr(vector<int> &arr1, vector<int> &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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.