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.

Description Hints 1 Solution Video 34:09

1131. Maximum of Absolute Value Expression

Medium49.0% acceptance2 companies

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

Asked at 2 companies

Microsoft

Google

Topics

Array Math

Hints open one at a time

Hint 1

Use the idea that abs(A) + abs(B) = max(A+B, A-B, -A+B, -A-B).

34:09

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,2,3,4]
[-1,4,5,6]

Input

[1,-2,-5,0,10]
[0,-2,-1,-7,-4]

Your code is saved on this device.Solution