Maximum of Absolute Value Expression solution and explanation
Google
5 more videos on this problem
1131. Maximum of Absolute Value Expression (Leetcode Medium)Programming Live with Larry · 34:09 · 1K views
Leetcode 1131 | Maximum of Absolute Value ExpressionMathematics · 35:54 · 1K views
【每日一题】1131. Maximum of Absolute Value Expression, 11/22/2019Huifeng Guan · 43:49 · 803 views
Maximum of Absolute Value Expression, Medium, LeetCode 1131 (Revisited!)H William Polenz · 26:07 · 136 views
LeetCode 1131: Maximum of Absolute Value ExpressionAlitaCode · 29:30 · 39 views
No Sound Leetcode 1131: Maximum of Absolute Value ExpressionExtremeProgrammer · 3:16 · 29 views
The 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
Approach overview
Problem 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 1: Approach 1: Separate Absolute Values into Multiple Cases
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.
def maxAbsValExpr(arr1, arr2):
maxVal = 0
signs = [[1, 1, 1], [1, -1, 1], [-1, 1, 1], [-1, -1, 1]]
for sign in signs:
maxSum = float('-inf')
minSum = float('inf')
for i in range(len(arr1)):
sum_val = arr1[i] * sign[0] + arr2[i] * sign[1] + i * sign[2]
maxSum = max(maxSum, sum_val)
minSum = min(minSum, sum_val)
maxVal = max(maxVal, maxSum - minSum)
return maxVal
# Example usage:
arr1 = [1, 2, 3, 4]
arr2 = [-1, 4, 5, 6]
print(maxAbsValExpr(arr1, arr2))class Solution {
public int maxAbsValExpr(int[] arr1, int[] arr2) {
int maxVal = 0;
int[][] signs = {{1, 1, 1}, {1, -1, 1}, {-1, 1, 1}, {-1, -1, 1}};
for (int[] sign : signs) {
int maxSum = Integer.MIN_VALUE;
int minSum = Integer.MAX_VALUE;
for (int i = 0; i < arr1.length; i++) {
int sum = arr1[i] * sign[0] + arr2[i] * sign[1] + i * sign[2];
maxSum = Math.max(maxSum, sum);
minSum = Math.min(minSum, sum);
}
maxVal = Math.max(maxVal, maxSum - minSum);
}
return maxVal;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] arr1 = {1, 2, 3, 4};
int[] arr2 = {-1, 4, 5, 6};
System.out.println(solution.maxAbsValExpr(arr1, arr2));
}
}#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) {
int maxVal = 0;
vector<vector<int>> signs = {{1, 1, 1}, {1, -1, 1}, {-1, 1, 1}, {-1, -1, 1}};
for (auto sign : signs) {
int maxSum = INT_MIN;
int minSum = INT_MAX;
for (int i = 0; i < arr1.size(); i++) {
int sum = arr1[i] * sign[0] + arr2[i] * sign[1] + i * sign[2];
maxSum = max(maxSum, sum);
minSum = min(minSum, sum);
}
maxVal = max(maxVal, maxSum - minSum);
}
return maxVal;
}
int main() {
vector<int> arr1 = {1, 2, 3, 4};
vector<int> arr2 = {-1, 4, 5, 6};
int result = maxAbsValExpr(arr1, arr2);
printf("%d\n", result);
return 0;
}const maxAbsValExpr = (arr1, arr2) => {
let maxVal = 0;
const signs = [[1, 1, 1], [1, -1, 1], [-1, 1, 1], [-1, -1, 1]];
for (let sign of signs) {
let maxSum = -Infinity;
let minSum = Infinity;
for (let i = 0; i < arr1.length; i++) {
let sum = arr1[i] * sign[0] + arr2[i] * sign[1] + i * sign[2];
maxSum = Math.max(maxSum, sum);
minSum = Math.min(minSum, sum);
}
maxVal = Math.max(maxVal, maxSum - minSum);
}
return maxVal;
};
// Example usage
const arr1 = [1, 2, 3, 4];
const arr2 = [-1, 4, 5, 6];
console.log(maxAbsValExpr(arr1, arr2));#include <stdio.h>
#include <stdlib.h>
int maxAbsValExpr(int* arr1, int arr1Size, int* arr2, int arr2Size) {
int maxVal = 0;
int signs[4][3] = {{1, 1, 1}, {1, -1, 1}, {-1, 1, 1}, {-1, -1, 1}};
for (int s = 0; s < 4; s++) {
int maxSum = INT_MIN;
int minSum = INT_MAX;
for (int i = 0; i < arr1Size; i++) {
int sum = arr1[i] * signs[s][0] + arr2[i] * signs[s][1] + i * signs[s][2];
if (sum > maxSum) maxSum = sum;
if (sum < minSum) minSum = sum;
}
int currentMax = maxSum - minSum;
if (currentMax > maxVal) maxVal = currentMax;
}
return maxVal;
}
int main() {
int arr1[] = {1, 2, 3, 4};
int arr2[] = {-1, 4, 5, 6};
int result = maxAbsValExpr(arr1, 4, arr2, 4);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public int MaxAbsValExpr(int[] arr1, int[] arr2) {
int maxVal = 0;
int[][] signs = new int[4][] {
new int[] {1, 1, 1},
new int[] {1, -1, 1},
new int[] {-1, 1, 1},
new int[] {-1, -1, 1}
};
foreach (var sign in signs) {
int maxSum = int.MinValue;
int minSum = int.MaxValue;
for (int i = 0; i < arr1.Length; i++) {
int sum = arr1[i] * sign[0] + arr2[i] * sign[1] + i * sign[2];
maxSum = Math.Max(maxSum, sum);
minSum = Math.Min(minSum, sum);
}
maxVal = Math.Max(maxVal, maxSum - minSum);
}
return maxVal;
}
public static void Main() {
int[] arr1 = {1, 2, 3, 4};
int[] arr2 = {-1, 4, 5, 6};
Solution solution = new Solution();
Console.WriteLine(solution.MaxAbsValExpr(arr1, arr2));
}
}The Python implementation follows the familiar steps of breaking the problem down according to sign manipulation, calculating the maximum differences from minimal expressions, in order to obtain the desired result.
Time Complexity is O(N) due to linear traversal of the arrays.
Space Complexity is O(1), as constant space is used for computational elements.
Approach 2: Approach 2: Optimizing with Mathematical Factorization
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.
def maxAbsValExpr(arr1, arr2):
maxA = maxB = maxC = maxD = float('-inf')
minA = minB = minC = minD = float('inf')
for i, (a, b) in enumerate(zip(arr1, arr2)):
A = a + b + i
B = a - b + i
C = -a + b + i
D = -a - b + i
maxA = max(maxA, A)
minA = min(minA, A)
maxB = max(maxB, B)
minB = min(minB, B)
maxC = max(maxC, C)
minC = min(minC, C)
maxD = max(maxD, D)
minD = min(minD, D)
return max(maxA - minA, maxB - minB, maxC - minC, maxD - minD)
# Testing
arr1 = [1, 2, 3, 4]
arr2 = [-1, 4, 5, 6]
print(maxAbsValExpr(arr1, arr2))class Solution {
public int maxAbsValExpr(int[] arr1, int[] arr2) {
int maxA = Integer.MIN_VALUE, maxB = Integer.MIN_VALUE, maxC = Integer.MIN_VALUE, maxD = Integer.MIN_VALUE;
int minA = Integer.MAX_VALUE, minB = Integer.MAX_VALUE, minC = Integer.MAX_VALUE, minD = Integer.MAX_VALUE;
for (int i = 0; i < arr1.length; i++) {
int A = arr1[i] + arr2[i] + i;
int B = arr1[i] - arr2[i] + i;
int C = -arr1[i] + arr2[i] + i;
int D = -arr1[i] - arr2[i] + i;
maxA = Math.max(maxA, A);
minA = Math.min(minA, A);
maxB = Math.max(maxB, B);
minB = Math.min(minB, B);
maxC = Math.max(maxC, C);
minC = Math.min(minC, C);
maxD = Math.max(maxD, D);
minD = Math.min(minD, D);
}
return Math.max(Math.max(maxA - minA, maxB - minB), Math.max(maxC - minC, maxD - minD));
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] arr1 = {1, 2, 3, 4};
int[] arr2 = {-1, 4, 5, 6};
System.out.println(solution.maxAbsValExpr(arr1, arr2));
}
}#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std;
int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) {
int maxA = INT_MIN, maxB = INT_MIN, maxC = INT_MIN, maxD = INT_MIN;
int minA = INT_MAX, minB = INT_MAX, minC = INT_MAX, minD = INT_MAX;
for (int i = 0; i < arr1.size(); i++) {
int A = arr1[i] + arr2[i] + i;
int B = arr1[i] - arr2[i] + i;
int C = -arr1[i] + arr2[i] + i;
int D = -arr1[i] - arr2[i] + i;
maxA = max(maxA, A);
minA = min(minA, A);
maxB = max(maxB, B);
minB = min(minB, B);
maxC = max(maxC, C);
minC = min(minC, C);
maxD = max(maxD, D);
minD = min(minD, D);
}
return max({maxA - minA, maxB - minB, maxC - minC, maxD - minD});
}
int main() {
vector<int> arr1 = {1, 2, 3, 4};
vector<int> arr2 = {-1, 4, 5, 6};
int result = maxAbsValExpr(arr1, arr2);
printf("%d\n", result);
return 0;
}const maxAbsValExpr = (arr1, arr2) => {
let maxA = -Infinity, maxB = -Infinity, maxC = -Infinity, maxD = -Infinity;
let minA = Infinity, minB = Infinity, minC = Infinity, minD = Infinity;
for (let i = 0; i < arr1.length; i++) {
let A = arr1[i] + arr2[i] + i;
let B = arr1[i] - arr2[i] + i;
let C = -arr1[i] + arr2[i] + i;
let D = -arr1[i] - arr2[i] + i;
maxA = Math.max(maxA, A);
minA = Math.min(minA, A);
maxB = Math.max(maxB, B);
minB = Math.min(minB, B);
maxC = Math.max(maxC, C);
minC = Math.min(minC, C);
maxD = Math.max(maxD, D);
minD = Math.min(minD, D);
}
return Math.max(maxA - minA, maxB - minB, maxC - minC, maxD - minD);
};
// Example usage
const arr1 = [1, 2, 3, 4];
const arr2 = [-1, 4, 5, 6];
console.log(maxAbsValExpr(arr1, arr2));#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int maxAbsValExpr(int* arr1, int arr1Size, int* arr2, int arr2Size) {
int maxA, maxB, maxC, maxD, minA, minB, minC, minD;
maxA = maxB = maxC = maxD = INT_MIN;
minA = minB = minC = minD = INT_MAX;
for (int i = 0; i < arr1Size; i++) {
int A = arr1[i] + arr2[i] + i;
int B = arr1[i] - arr2[i] + i;
int C = -arr1[i] + arr2[i] + i;
int D = -arr1[i] - arr2[i] + i;
if (A > maxA) maxA = A;
if (A < minA) minA = A;
if (B > maxB) maxB = B;
if (B < minB) minB = B;
if (C > maxC) maxC = C;
if (C < minC) minC = C;
if (D > maxD) maxD = D;
if (D < minD) minD = D;
}
int resA = maxA - minA;
int resB = maxB - minB;
int resC = maxC - minC;
int resD = maxD - minD;
return (resA > resB ? (resA > resC ? (resA > resD ? resA : resD) : (resC > resD ? resC : resD)) : (resB > resC ? (resB > resD ? resB : resD) : (resC > resD ? resC : resD)));
}
int main() {
int arr1[] = {1, 2, 3, 4};
int arr2[] = {-1, 4, 5, 6};
int result = maxAbsValExpr(arr1, 4, arr2, 4);
printf("%d\n", result);
return 0;
}using System;
public class Solution {
public int MaxAbsValExpr(int[] arr1, int[] arr2) {
int maxA = int.MinValue, maxB = int.MinValue, maxC = int.MinValue, maxD = int.MinValue;
int minA = int.MaxValue, minB = int.MaxValue, minC = int.MaxValue, minD = int.MaxValue;
for (int i = 0; i < arr1.Length; i++) {
int A = arr1[i] + arr2[i] + i;
int B = arr1[i] - arr2[i] + i;
int C = -arr1[i] + arr2[i] + i;
int D = -arr1[i] - arr2[i] + i;
maxA = Math.Max(maxA, A);
minA = Math.Min(minA, A);
maxB = Math.Max(maxB, B);
minB = Math.Min(minB, B);
maxC = Math.Max(maxC, C);
minC = Math.Min(minC, C);
maxD = Math.Max(maxD, D);
minD = Math.Min(minD, D);
}
return Math.Max(Math.Max(maxA - minA, maxB - minB), Math.Max(maxC - minC, maxD - minD));
}
public static void Main() {
int[] arr1 = {1, 2, 3, 4};
int[] arr2 = {-1, 4, 5, 6};
Solution solution = new Solution();
Console.WriteLine(solution.MaxAbsValExpr(arr1, arr2));
}
}The Python solution utilizes tuples inclusive of index computations to navigate A, B, C, and D conditions. Guarding against errors with inherent floating point settings, it evokes the best derivation from possible factual state differences.
Time Complexity: O(N) given the linear assessment through generators.
Space Complexity: O(1), calculations are self-contained minimizing dynamic span.
Approach 3: Mathematics + Enumeration
Let's denote x_i = arr1[i], y_i = arr2[i]. Since the size relationship between i and j does not affect the value of the expression, we can assume i \ge j. Then the expression can be transformed into:
$
| x_i - x_j | + | y_i - y_j | + i - j = max \begin{cases} (x_i + y_i) - (x_j + y_j) \ (x_i - y_i) - (x_j - y_j) \ (-x_i + y_i) - (-x_j + y_j) \ (-x_i - y_i) - (-x_j - y_j) \end{cases} + i - j\
= max \begin{cases} (x_i + y_i + i) - (x_j + y_j + j) \ (x_i - y_i + i) - (x_j - y_j + j) \ (-x_i + y_i + i) - (-x_j + y_j + j) \ (-x_i - y_i + i) - (-x_j - y_j + j) \end{cases}
Therefore, we just need to find the maximum value mx and the minimum value mi of a times x_i + b times y_i + i, where a, b \in {-1, 1}. The answer is the maximum value among all mx - mi.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1)$.
Similar problems:
function maxAbsValExpr(arr1: number[], arr2: number[]): number {
const dirs = [1, -1, -1, 1, 1];
const inf = 1 << 30;
let ans = -inf;
for (let k = 0; k < 4; ++k) {
const [a, b] = [dirs[k], dirs[k + 1]];
let mx = -inf;
let mi = inf;
for (let i = 0; i < arr1.length; ++i) {
const [x, y] = [arr1[i], arr2[i]];
mx = Math.max(mx, a * x + b * y + i);
mi = Math.min(mi, a * x + b * y + i);
ans = Math.max(ans, mx - mi);
}
}
return ans;
}func maxAbsValExpr(arr1 []int, arr2 []int) int {
dirs := [5]int{1, -1, -1, 1, 1}
const inf = 1 << 30
ans := -inf
for k := 0; k < 4; k++ {
a, b := dirs[k], dirs[k+1]
mx, mi := -inf, inf
for i, x := range arr1 {
y := arr2[i]
mx = max(mx, a*x+b*y+i)
mi = min(mi, a*x+b*y+i)
ans = max(ans, mx-mi)
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Separate Absolute Values into Multiple Cases | Time Complexity is O(N) due to linear traversal of the arrays. |
| Approach 2: Optimizing with Mathematical Factorization | Time Complexity: O(N) given the linear assessment through generators. |
| Mathematics + Enumeration | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Maximum of Absolute Value Expression easy or hard?
The problem is rated Medium because the implementation is simple once the mathematical insight is known. The difficulty comes from recognizing how to convert multiple absolute values into a small set of linear expressions.
Maximum of Absolute Value Expression Python/Java solution
Python and Java implementations both compute four transformed expressions during a single pass through the arrays. Each iteration updates min and max values for the current transformation. The final answer is the largest difference found across all cases.
How to solve Maximum of Absolute Value Expression in O(n)?
Rewrite |arr1[i]-arr1[j]| + |arr2[i]-arr2[j]| + |i-j| into four expressions based on sign combinations. For each form, compute a transformed value like arr1[i] + arr2[i] + i while iterating through the array. Track the minimum and maximum values, and the difference between them gives the maximum possible result.
What is the best approach for Maximum of Absolute Value Expression?
The optimal approach transforms the expression into four linear forms such as arr1[i] + arr2[i] + i and tracks the maximum and minimum values during a single pass. This eliminates the need to check all index pairs. The algorithm runs in O(n) time with O(1) extra space.
Is Maximum of Absolute Value Expression asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies like Google, Amazon, and Meta because it tests algebraic reasoning and array traversal optimization. The key skill is recognizing how to simplify absolute value expressions into linear forms.
What data structure is used in Maximum of Absolute Value Expression?
The solution mainly uses arrays and simple variables to track running minimum and maximum values. No advanced data structures are required; the challenge lies in mathematical transformation rather than storage.
What is the time complexity of Maximum of Absolute Value Expression?
The optimal solution runs in O(n) time because the array is scanned a constant number of times (four transformations). Each scan updates minimum and maximum values. Space complexity is O(1) since only a few variables are maintained.