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.
The expression |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j| can be viewed as a combination of absolute differences. Absolute differences can be handled by considering both cases for positive and negative differences.
Let's break it into manageable expressions:
1. (arr1[i] - arr1[j]) can be positive or negative
2. (arr2[i] - arr2[j]) can be positive or negative
3. (i - j) can be positive or negative
Which leads us to 23 = 8 cases, but since only four sign patterns are distinct (accounting for permutations which result in the same number), we can limit the number of calculations.
This C implementation iterates through different sign combinations and calculates the expressions corresponding to those signs. We calculate sum for each element using respective signs, and track the maximum and minimum of these sums. The answer is the maximum difference obtained across all scenarios, computed as maxSum - minSum.
Time Complexity: O(N), where N is the length of the array, since we process each element only once for each of the sign cases.
Space Complexity: O(1), as we use a fixed extra space for variables.
Given the nature of the expression and its constraints, we can approach the problem by mathematical factoring. For each pair of the function's operands, deconstruct the absolute values by optimizing via logical indexing into distinct mathematical subproblems.
This translates into simplifying repetitious calculations and honing in on maximum viable outcomes.
In the optimized C version, we directly evaluate four transformed conditions: A, B, C, and D, which are representative of the expression's scenarios. Storing min-max results, we compute the greatest difference among these calculated states.
Time Complexity: O(N), the logic iterates once through the arrays.
Space Complexity: O(1), since it involves constant space.
| Approach | Complexity |
|---|---|
| Approach 1: Separate Absolute Values into Multiple Cases | Time Complexity: O(N), where N is the length of the array, since we process each element only once for each of the sign cases. |
| Approach 2: Optimizing with Mathematical Factorization | Time Complexity: O(N), the logic iterates once through the arrays. |
| 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. |
1131. Maximum of Absolute Value Expression (Leetcode Medium) • Programming Live with Larry • 1,582 views views
Watch 5 more video solutions →Practice Maximum of Absolute Value Expression with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor