We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum of Absolute Value Expression

Difficulty: Medium

Problem Description

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.

Key Insights

  • The expression can be expanded and analyzed in terms of the possible combinations of signs.
  • We can derive four variations of the expression that essentially encapsulate all possible combinations of signs for the absolute values.
  • Instead of checking every pair (i, j), we can compute these variations in a single pass, which leads to an efficient solution.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we can express the absolute value terms in four different ways based on the signs:

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

By iterating through the arrays, we can compute the maximum and minimum for each of these four expressions, and the maximum value will be the result. This approach allows us to achieve the solution in linear time.

Code Solutions

def maxAbsValExpr(arr1, arr2):
    max_value = 0
    n = len(arr1)
    
    for sign1 in [1, -1]:
        for sign2 in [1, -1]:
            current_max = float('-inf')
            current_min = float('inf')
            for i in range(n):
                value = sign1 * arr1[i] + sign2 * arr2[i] + i
                current_max = max(current_max, value)
                current_min = min(current_min, value)
            max_value = max(max_value, current_max - current_min)
    
    return max_value
← Back to All Questions