Skip to main content
Talentd

Maximum of Absolute Value Expression - Solution & Explanation

MediumArrayMath23 min readAsked at: Microsoft, Google
Practice this problem

Problem Statement

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(N), the logic iterates once through the arrays.
Space Complexity: O(1), since it involves constant space.

Try this approach in the editor →

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:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(1), as we use a fixed extra space for variables.

Approach 2: Optimizing with Mathematical Factorization

Time Complexity: O(N), the logic iterates once through the arrays.
Space Complexity: O(1), since it involves constant space.

Mathematics + Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Separate Absolute Values into Multiple CasesO(n)O(1)Best general solution. Expands absolute values into four expressions and scans arrays once.
Mathematical FactorizationO(n)O(1)Preferred interview explanation. Uses algebraic transformation and Manhattan distance insight.

Video Solution

1131. Maximum of Absolute Value Expression (Leetcode Medium) • Programming Live with Larry • 1,613 views views

Watch 5 more video solutions →

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.

Ready to solve this problem?

Practice Maximum of Absolute Value Expression with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays