Maximum of Absolute Value Expression: Sign Expansion Pattern

You are given two arrays of integers arr1 and arr2 of the same length. Find the maximum value of |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j| over all pairs 0 <= i, j < arr1.length. This is LeetCode 1131: Maximum of Absolute Value Expression.

Example: arr1 = [1, 2, 3, 4], arr2 = [-1, 4, 5, 6] returns 13 from the pair (0, 3): |1-4| + |-1-6| + |0-3| = 3 + 7 + 3 = 13.

Why this problem matters

The brute force approach checks every pair (i, j) and computes the expression for each. That is O(n^2), and with arrays up to 40,000 elements long, it will not pass. The problem is really asking: can you see through the absolute values to find a way to evaluate the expression in linear time?

This is a textbook example of sign expansion, a technique where you remove absolute values by considering all possible sign combinations. The same idea appears in problems involving Manhattan distance, absolute difference sums, and geometric distance optimization. Once you recognize that |a| equals max(a, -a), you can expand any sum of absolute values into a finite set of linear expressions and optimize each one independently.

The sign expansion pattern is closely related to formula decomposition from problems like Best Sightseeing Pair. In that problem, you split a pair-score formula into terms that depend on only one index. Here, you do the same thing, but first you need to remove the absolute values before the decomposition becomes visible.

The key insight

The expression |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j| has three absolute values. Each absolute value can be resolved in two ways: the quantity inside is either non-negative or negative. That gives 2^3 = 8 sign combinations.

For each combination, the expression becomes something like:

(s1 * arr1[i] + s2 * arr2[i] + s3 * i) - (s1 * arr1[j] + s2 * arr2[j] + s3 * j)

where s1, s2, s3 are each +1 or -1. Define f(k) = s1 * arr1[k] + s2 * arr2[k] + s3 * k. Then the expression for a given sign combo is f(i) - f(j), and the maximum of this over all i and j is simply max(f) - min(f).

So the algorithm becomes: for each of the 8 sign combinations, compute f(k) for every index, find the max and min, and take the difference. The overall answer is the largest such difference across all 8 combos.

Since each combo is a mirror of another (flipping all three signs gives the same max-min), you only need 4 combos. But computing all 8 works fine and the code is cleaner.

The solution

def max_abs_val_expr(arr1, arr2):
    n = len(arr1)
    result = 0
    for s1 in [1, -1]:
        for s2 in [1, -1]:
            for s3 in [1, -1]:
                max_val = float('-inf')
                min_val = float('inf')
                for i in range(n):
                    val = s1 * arr1[i] + s2 * arr2[i] + s3 * i
                    max_val = max(max_val, val)
                    min_val = min(min_val, val)
                result = max(result, max_val - min_val)
    return result

Here is what each piece does:

1. Loop over all 8 sign combinations. Three nested loops over [1, -1] produce all eight (s1, s2, s3) tuples.
2. Compute f(i) for each index. For a given sign combo, f(i) = s1 * arr1[i] + s2 * arr2[i] + s3 * i.
3. Track max and min of f. A single pass finds both.
4. Update the result. The max-min difference for this combo is a candidate answer. Keep the best.

The outer loop runs 8 times, the inner loop runs n times, so the total work is 8 * n = O(n).

Visual walkthrough

The walkthrough shows the four key steps: expand the absolute values into sign combinations, group terms by index to get a function f(i), compute max minus min for each combo in a single pass, and take the best result. For this input, the (+,+,+) combo gives the largest spread of 13.

Complexity analysis

Time is O(n) because you make 8 passes through the array (one per sign combo), and 8 is a constant. Each pass does O(1) work per element.

Space is O(1) because you only store a few variables per combo: the current max, current min, and the running result. No auxiliary arrays needed.

The building blocks

1. Sign expansion for absolute values

The core technique is removing absolute values by enumerating sign combinations. Every |a - b| can be written as max(a - b, b - a), which means you consider both signs. When you have multiple absolute values summed together, you enumerate all combinations.

For k absolute values, you get 2^k combos. In this problem k=3, giving 8. In Manhattan distance problems you often have k=2, giving 4. The pattern is the same: expand, compute a linear function for each combo, and optimize.

This pattern shows up in any problem where you need to maximize or minimize a sum of absolute differences. Instead of wrestling with case analysis, you enumerate all cases systematically and reduce each one to a simple max or max-min computation.

2. Running max and min tracking

Once you have a linear function f(i) for each combo, maximizing f(i) - f(j) over all pairs is just max(f) - min(f). You find both in a single pass with two variables.

max_val = float('-inf')
min_val = float('inf')
for i in range(n):
    val = f(i)
    max_val = max(max_val, val)
    min_val = min(min_val, val)
spread = max_val - min_val

This is the same running-extremum pattern from Best Time to Buy and Sell Stock and Best Sightseeing Pair. Track the best and worst you have seen so far. Use them at the end (or along the way) to compute the answer.

3. Formula decomposition

After sign expansion, each combo produces f(i) - f(j). This is a separable formula where one side depends only on i and the other only on j. That separability is what lets you optimize in O(n) instead of O(n^2).

The decomposition insight is the same one behind Best Sightseeing Pair, where the score splits into (values[i] + i) + (values[j] - j). Here the split is even simpler: f(i) - f(j), and the maximum is just the spread of f.

Edge cases

• Length 1: with a single element, every pair has i == j, so all absolute differences are 0. The answer is 0.
• Identical arrays: if arr1 and arr2 are the same, the expression simplifies to 2 * |arr1[i] - arr1[j]| + |i - j|. The sign expansion still works correctly.
• All zeros: both arrays are all zeros. The expression reduces to |i - j|, and the answer is n - 1.
• Large negative values: elements can range from -10^6 to 10^6. The sign expansion handles negatives naturally since it considers both + and - signs.
• Two elements: only one pair exists (i=0, j=1). The answer is |arr1[0] - arr1[1]| + |arr2[0] - arr2[1]| + 1.

From understanding to recall

You have seen the sign expansion: remove the absolute values by trying all 8 sign combos, compute f(i) = s1*arr1[i] + s2*arr2[i] + s3*i, then take max(f) - min(f) for each combo. The idea is clean and the code is a few nested loops. Understanding it takes minutes.

But reproducing it under interview pressure is a different skill. You need to remember that three absolute values give eight combos, that each combo reduces to a max-min problem, and that the whole thing runs in O(n). These details slip away if you only read about them once.

Spaced repetition bridges this gap. You practice writing the sign expansion and the max-min loop from scratch at increasing intervals. After a few rounds, the pattern locks in. You see a sum of absolute differences and the expansion comes automatically: enumerate signs, define f, track max and min, sweep once. No fumbling, no second-guessing the number of combos.

The sign expansion pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning each one in isolation and drilling it with spaced repetition is far more effective than grinding random problems and hoping the insight sticks.

Related posts

• Best Sightseeing Pair - Formula decomposition with a running max, the same core trick after you expand the signs
• Maximum Subarray - Kadane's algorithm uses a running optimum to avoid checking all subarrays
• Best Time to Buy and Sell Stock - Track a running minimum while iterating, the simplest form of the max-min spread pattern

CodeBricks breaks the maximum of absolute value expression problem into its sign expansion and running max-min building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a sum-of-absolute-values optimization question shows up in your interview, you do not think about it. You just write it.