LeetCode 1131 - Maximum of Absolute Value Expression

The problem gives us two integer arrays, arr1 and arr2, both having the same length. We must compute the maximum possible value of the following expression across every pair of indices (i, j): The task is not asking for the indices themselves, only the largest achievable value.

leetcodemediumarraymath

LeetCode Problem 1131

Difficulty: 🟡 Medium
Topics: Array, Math

Solution

Problem Understanding

The problem gives us two integer arrays, arr1 and arr2, both having the same length. We must compute the maximum possible value of the following expression across every pair of indices (i, j):

$$|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|$$

The task is not asking for the indices themselves, only the largest achievable value.

At first glance, this looks like a direct application of absolute value calculations across all pairs of elements. Since there are n elements, there are n^2 possible (i, j) combinations. For small arrays, checking every pair would work, but the constraints allow array sizes up to 40000, which makes quadratic solutions too slow.

The input represents two coordinate-like arrays. For each index i, we can think of the point:

$$(arr1[i], arr2[i], i)$$

The expression measures a Manhattan distance between two such points in three-dimensional space.

The output is a single integer, the maximum value obtainable from any valid pair of indices.

The constraints provide several important observations:

  • arr1.length == arr2.length, so every index exists in both arrays.
  • The maximum array size is 40000, which strongly suggests we need a linear or near-linear algorithm.
  • Values may be negative, so we must handle sign changes carefully.
  • Absolute values are the key challenge, because they create multiple possible sign combinations.

Several edge cases are important:

  • Arrays containing negative numbers, because sign handling becomes critical.
  • Arrays where all values are identical, where the index difference alone determines the result.
  • Very small arrays of length 2, where only one meaningful pair exists.
  • Large magnitude values near 10^6, where overflow concerns matter in some languages.
  • Cases where the optimal answer comes from mixing positive and negative differences across dimensions.

Approaches

Brute Force Approach

The most straightforward solution is to evaluate the expression for every pair (i, j).

For each pair, we compute:

$$|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|$$

and keep track of the maximum value encountered.

This approach is correct because it explicitly checks every possible candidate pair, so it cannot miss the optimal answer.

However, the time complexity is too high. With n elements, there are n^2 pairs. When n = 40000, this becomes:

$$40000^2 = 1.6 \times 10^9$$

which is far beyond acceptable limits for LeetCode time constraints.

Optimal Approach

The key observation is that absolute values can be rewritten using sign combinations.

Consider the expression:

$$|a-b| + |c-d| + |i-j|$$

Each absolute value can contribute either positively or negatively depending on ordering. Expanding all possible sign choices gives only a fixed number of linear forms.

For this problem, the expression can always be transformed into one of these forms:

$$(\pm arr1[i]) + (\pm arr2[i]) + i$$

More specifically, only four unique combinations matter:

  1. arr1[i] + arr2[i] + i
  2. arr1[i] + arr2[i] - i
  3. arr1[i] - arr2[i] + i
  4. arr1[i] - arr2[i] - i

For any one of these forms, the maximum difference between two indices is simply:

$$\max(expression) - \min(expression)$$

So instead of checking all pairs, we iterate through the array once for each sign combination, track the minimum and maximum value, and compute their difference.

This transforms the problem from quadratic complexity to linear complexity.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Checks every pair directly
Optimal O(n) O(1) Uses sign transformation and max-min tracking

Algorithm Walkthrough

  1. Observe that the expression contains three absolute values.

The expression is:

$$|arr1[i]-arr1[j]| + |arr2[i]-arr2[j]| + |i-j|$$

Each absolute value can behave as either positive or negative depending on which operand is larger. 2. Rewrite the expression using sign combinations.

Expanding the possibilities leads to four distinct linear expressions:

$$arr1[i] + arr2[i] + i$$

$$arr1[i] + arr2[i] - i$$

$$arr1[i] - arr2[i] + i$$

$$arr1[i] - arr2[i] - i$$

Any valid value of the original expression corresponds to the difference between two values from one of these forms. 3. Process each form independently.

For each expression type:

  • Compute the value for every index.
  • Track the smallest value seen so far.
  • Track the largest value seen so far.
  1. Compute the best difference.

The maximum possible difference for that form is:

$$maxValue - minValue$$ 5. Keep the global maximum.

Compare the result from all four forms and return the largest one.

Why it works

The correctness comes from the fact that Manhattan distance expressions can be represented as the maximum difference among several linear transformations. Every possible combination of absolute value signs is covered by one of the four forms. Since the optimal pair must maximize one of these transformed expressions, taking the difference between the maximum and minimum transformed values guarantees we find the true answer.

Python Solution

from typing import List

class Solution:
    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
        n = len(arr1)
        
        expressions = [
            lambda a, b, i: a + b + i,
            lambda a, b, i: a + b - i,
            lambda a, b, i: a - b + i,
            lambda a, b, i: a - b - i,
        ]
        
        answer = 0
        
        for expression in expressions:
            minimum = float('inf')
            maximum = float('-inf')
            
            for i in range(n):
                value = expression(arr1[i], arr2[i], i)
                
                minimum = min(minimum, value)
                maximum = max(maximum, value)
            
            answer = max(answer, maximum - minimum)
        
        return answer

The implementation begins by defining the four transformed expressions that represent all meaningful sign combinations.

For each transformation, the algorithm scans the arrays once. During the scan, it computes the transformed value for the current index and updates the running minimum and maximum.

After processing all indices for a given form, the difference between the largest and smallest transformed values represents the best possible contribution from that form.

The global answer stores the best result across all four transformations.

The solution uses constant extra memory because it only maintains a few variables while iterating.

Go Solution

func maxAbsValExpr(arr1 []int, arr2 []int) int {
	n := len(arr1)

	maximum := func(a, b int) int {
		if a > b {
			return a
		}
		return b
	}

	result := 0

	for k := 0; k < 4; k++ {
		minVal := int(1e9)
		maxVal := -int(1e9)

		for i := 0; i < n; i++ {
			var value int

			switch k {
			case 0:
				value = arr1[i] + arr2[i] + i
			case 1:
				value = arr1[i] + arr2[i] - i
			case 2:
				value = arr1[i] - arr2[i] + i
			case 3:
				value = arr1[i] - arr2[i] - i
			}

			if value < minVal {
				minVal = value
			}

			if value > maxVal {
				maxVal = value
			}
		}

		result = maximum(result, maxVal-minVal)
	}

	return result
}

The Go implementation follows the same logic as the Python version but uses a switch statement instead of lambda functions.

Go does not provide built-in min and max functions for integers in older versions, so comparisons are handled manually.

Integer overflow is not a concern here because the maximum possible transformed value remains comfortably within 32-bit signed integer range:

$$10^6 + 10^6 + 40000 < 2^{31}$$

The solution still uses int, which is standard and sufficient for LeetCode.

Worked Examples

Example 1

arr1 = [1,2,3,4]
arr2 = [-1,4,5,6]

We evaluate all four transformed expressions.

Expression 1: arr1[i] + arr2[i] + i

i arr1[i] arr2[i] Value
0 1 -1 0
1 2 4 7
2 3 5 10
3 4 6 13
  • Minimum = 0
  • Maximum = 13
  • Difference = 13

Expression 2: arr1[i] + arr2[i] - i

i Value
0 0
1 5
2 6
3 7
  • Difference = 7

Expression 3: arr1[i] - arr2[i] + i

i Value
0 2
1 -1
2 0
3 1
  • Difference = 3

Expression 4: arr1[i] - arr2[i] - i

i Value
0 2
1 -3
2 -4
3 -5
  • Difference = 7

The maximum among all forms is:

$$13$$

So the answer is:

13

Example 2

arr1 = [1,-2,-5,0,10]
arr2 = [0,-2,-1,-7,-4]

Expression 1: arr1[i] + arr2[i] + i

i Value
0 1
1 -3
2 -4
3 -4
4 10
  • Minimum = -4
  • Maximum = 10
  • Difference = 14

Expression 2: arr1[i] + arr2[i] - i

i Value
0 1
1 -5
2 -8
3 -10
4 2
  • Difference = 12

Expression 3: arr1[i] - arr2[i] + i

i Value
0 1
1 1
2 -2
3 10
4 18
  • Minimum = -2
  • Maximum = 18
  • Difference = 20

Expression 4: arr1[i] - arr2[i] - i

i Value
0 1
1 -1
2 -6
3 4
4 10
  • Difference = 16

The maximum overall result is:

$$20$$

So the answer is:

20

Complexity Analysis

Measure Complexity Explanation
Time O(n) Four linear scans across the arrays
Space O(1) Only a few variables are stored

The algorithm processes the arrays four times, once for each sign configuration. Since four is a constant, the total running time remains linear in terms of n.

The space complexity is constant because no auxiliary data structures proportional to input size are allocated.

Test Cases

from typing import List

class Solution:
    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
        expressions = [
            lambda a, b, i: a + b + i,
            lambda a, b, i: a + b - i,
            lambda a, b, i: a - b + i,
            lambda a, b, i: a - b - i,
        ]

        answer = 0
        n = len(arr1)

        for expression in expressions:
            minimum = float('inf')
            maximum = float('-inf')

            for i in range(n):
                value = expression(arr1[i], arr2[i], i)

                minimum = min(minimum, value)
                maximum = max(maximum, value)

            answer = max(answer, maximum - minimum)

        return answer

solution = Solution()

assert solution.maxAbsValExpr(
    [1,2,3,4],
    [-1,4,5,6]
) == 13  # Provided example 1

assert solution.maxAbsValExpr(
    [1,-2,-5,0,10],
    [0,-2,-1,-7,-4]
) == 20  # Provided example 2

assert solution.maxAbsValExpr(
    [1,1],
    [1,1]
) == 1  # Only index difference contributes

assert solution.maxAbsValExpr(
    [-1,-2,-3],
    [-4,-5,-6]
) == 6  # All negative values

assert solution.maxAbsValExpr(
    [0,0,0],
    [0,0,0]
) == 2  # Maximum comes entirely from index distance

assert solution.maxAbsValExpr(
    [1000000,-1000000],
    [1000000,-1000000]
) == 4000001  # Large magnitude values

assert solution.maxAbsValExpr(
    [5,5,5,5],
    [5,5,5,5]
) == 3  # Constant arrays

assert solution.maxAbsValExpr(
    [1,3,6],
    [7,2,8]
) == 12  # Mixed positive values

assert solution.maxAbsValExpr(
    [-10,0,10],
    [10,0,-10]
) == 42  # Strong sign changes

print("All tests passed.")

Test Summary

Test Why
[1,2,3,4] and [-1,4,5,6] Validates provided example
[1,-2,-5,0,10] and [0,-2,-1,-7,-4] Validates provided example with negatives
[1,1] and [1,1] Smallest valid input size
All negative arrays Ensures sign handling is correct
All zero arrays Ensures index distance is handled properly
Large magnitude values Tests integer range handling
Constant arrays Ensures only index difference contributes
Mixed positive values General correctness case
Strong sign changes Stress test for absolute value transformations

Edge Cases

One important edge case occurs when all array values are identical. In that situation, the differences between array elements become zero, so the entire result depends only on |i - j|. A buggy implementation might accidentally ignore the index contribution when simplifying the formula. This implementation correctly includes the index in every transformed expression, so the maximum distance between indices is naturally considered.

Another critical edge case involves negative numbers. Absolute values with negative operands are often a source of mistakes because sign transformations can easily become incorrect. The four-expression transformation guarantees that every valid sign configuration is represented, so negative values are handled correctly without requiring special branching logic.

A third important edge case is very large integer values near the constraint limits. Since values can reach 10^6, combining multiple terms could overflow in some languages if smaller integer types were used. The implementation uses standard integer arithmetic safely because the maximum possible expression remains well within 32-bit signed integer limits.