Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1131. Maximum of Absolute Value Expression - Leetcode Solution

Code Implementation

class Solution:
    def maxAbsValExpr(self, arr1, arr2):
        res = 0
        n = len(arr1)
        for p, q in [(1,1), (1,-1), (-1,1), (-1,-1)]:
            max_val = float('-inf')
            min_val = float('inf')
            for i in range(n):
                value = p*arr1[i] + q*arr2[i] + i
                max_val = max(max_val, value)
                min_val = min(min_val, value)
            res = max(res, max_val - min_val)
        return res
      
class Solution {
public:
    int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) {
        int res = 0, n = arr1.size();
        int signs[2] = {1, -1};
        for (int p : signs) {
            for (int q : signs) {
                int maxVal = INT_MIN, minVal = INT_MAX;
                for (int i = 0; i < n; ++i) {
                    int value = p*arr1[i] + q*arr2[i] + i;
                    maxVal = max(maxVal, value);
                    minVal = min(minVal, value);
                }
                res = max(res, maxVal - minVal);
            }
        }
        return res;
    }
};
      
class Solution {
    public int maxAbsValExpr(int[] arr1, int[] arr2) {
        int res = 0, n = arr1.length;
        int[] signs = {1, -1};
        for (int p : signs) {
            for (int q : signs) {
                int maxVal = Integer.MIN_VALUE, minVal = Integer.MAX_VALUE;
                for (int i = 0; i < n; ++i) {
                    int value = p * arr1[i] + q * arr2[i] + i;
                    maxVal = Math.max(maxVal, value);
                    minVal = Math.min(minVal, value);
                }
                res = Math.max(res, maxVal - minVal);
            }
        }
        return res;
    }
}
      
var maxAbsValExpr = function(arr1, arr2) {
    let res = 0, n = arr1.length;
    let signs = [1, -1];
    for (let p of signs) {
        for (let q of signs) {
            let maxVal = -Infinity, minVal = Infinity;
            for (let i = 0; i < n; ++i) {
                let value = p * arr1[i] + q * arr2[i] + i;
                maxVal = Math.max(maxVal, value);
                minVal = Math.min(minVal, value);
            }
            res = Math.max(res, maxVal - minVal);
        }
    }
    return res;
};

Problem Description

Given two integer arrays arr1 and arr2, both of length n, you are asked to find the maximum value of the following expression for all pairs of indices i and j (where 0 ≤ i, j < n):

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

Your task is to compute this maximum value efficiently, considering that n can be large (up to 40,000). Each index can be paired with any other (including itself), and the arrays may contain both positive and negative integers.

Thought Process

At first glance, the problem seems to require checking every possible pair of indices (i, j), calculating the expression, and keeping track of the maximum. This brute-force approach would involve O(n^2) computations, which is not feasible for large arrays.

To optimize, we need to recognize patterns in the expression, especially how absolute values behave. The key insight is that the sum of absolute differences can be rewritten by considering all possible combinations of signs, which allows us to reduce the problem to a series of maximum and minimum value calculations over linear traversals, instead of nested loops.

Solution Approach

The main trick is to break down the absolute value expression using properties of absolute values:
  • For any two variables x and y, |x - y| = max(x - y, y - x).
  • For the sum |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|, we can expand it by considering all sign combinations.
The steps are:
  1. Observe that each absolute value can be either positive or negative, depending on which index is larger.
  2. For three terms, there are 23 = 8 sign combinations, but since |x - y| = |y - x|, only 4 unique combinations matter.
  3. For each combination of signs (p, q) where p, q ∈ {1, -1}, compute value = p*arr1[i] + q*arr2[i] + i for all i.
  4. For each combination, track the maximum and minimum values of value across all i.
  5. The maximum difference for each combination is max_value - min_value.
  6. The answer is the maximum of these four differences.
This reduces the time complexity to O(n), since each combination only requires a single pass through the arrays.

Example Walkthrough

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

Let's follow the steps:
  1. For the combination (p=1, q=1):
    • Compute arr1[i] + arr2[i] + i for each i:
      • i=0: 1 + (-1) + 0 = 0
      • i=1: 2 + 4 + 1 = 7
      • i=2: 3 + 5 + 2 = 10
      • i=3: 4 + 6 + 3 = 13
    • max = 13, min = 0, difference = 13
  2. Repeat for (1, -1):
    • i=0: 1 - (-1) + 0 = 2
    • i=1: 2 - 4 + 1 = -1
    • i=2: 3 - 5 + 2 = 0
    • i=3: 4 - 6 + 3 = 1
    • max = 2, min = -1, difference = 3
  3. For (-1, 1):
    • i=0: -1 + (-1) + 0 = -2
    • i=1: -2 + 4 + 1 = 3
    • i=2: -3 + 5 + 2 = 4
    • i=3: -4 + 6 + 3 = 5
    • max = 5, min = -2, difference = 7
  4. For (-1, -1):
    • i=0: -1 - (-1) + 0 = 0
    • i=1: -2 - 4 + 1 = -5
    • i=2: -3 - 5 + 2 = -6
    • i=3: -4 - 6 + 3 = -7
    • max = 0, min = -7, difference = 7
The maximum difference among all combinations is 13.

Time and Space Complexity

  • Brute-force: O(n^2) time, since every pair of indices is checked. Space is O(1) (ignoring input).
  • Optimized approach: O(n) time, since for each of the 4 sign combinations, we scan the arrays once. Space is O(1) extra (just variables for min/max).
The optimized method is efficient and suitable for large inputs.

Summary

The problem is elegantly solved by recognizing how absolute value expressions can be transformed through sign combinations. Instead of brute-force, we only need four linear passes through the arrays, tracking min and max for each case. This technique—reducing absolute value expressions to a small set of linear forms—is a powerful pattern for similar problems, allowing for optimal and readable solutions.