LeetCode Solutions Blog

Maximum of Absolute Value Expression

Number: 1230

Difficulty: Medium

Paid? No

Companies: Microsoft

Problem Description

Given two arrays of integers arr1 and arr2 of equal length, find the maximum value of: |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j| for all valid indices 0 <= i, j < arr1.length.

Key Insights

The expression involves absolute differences over three terms: two from the arrays and one from the indices.
By considering different sign combinations, we can transform the expression into four different linear forms.
Tracking the maximum and minimum values for each transformed expression allows for a direct calculation of the answer.
Only one pass through the arrays is necessary, resulting in an efficient O(n) solution.

Space and Time Complexity

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

Solution

We transform the original expression into four forms to account for different sign combinations:

T1(i) = arr1[i] + arr2[i] + i
T2(i) = arr1[i] + arr2[i] - i
T3(i) = arr1[i] - arr2[i] + i
T4(i) = arr1[i] - arr2[i] - i

For each transformation, iterate through the arrays keeping track of maximum and minimum values. The maximum difference for a transformed sequence is given by (max - min). The overall answer is the maximum among these four differences. This greedy approach avoids a double loop and efficiently computes the result in one pass.

Code Solutions

# Python solution for Maximum of Absolute Value Expression
def maxAbsValExpr(arr1, arr2):
    # Initialize variables to store maximum and minimum values for each transformation
    t1_max = t2_max = t3_max = t4_max = float('-inf')
    t1_min = t2_min = t3_min = t4_min = float('inf')
    
    # Process each index in arr1 and arr2
    for i in range(len(arr1)):
        a = arr1[i]
        b = arr2[i]
        # Transformations based on different sign combinations
        t1 = a + b + i
        t2 = a + b - i
        t3 = a - b + i
        t4 = a - b - i
        
        # Update t1 tracking
        t1_max = max(t1_max, t1)
        t1_min = min(t1_min, t1)
        
        # Update t2 tracking
        t2_max = max(t2_max, t2)
        t2_min = min(t2_min, t2)
        
        # Update t3 tracking
        t3_max = max(t3_max, t3)
        t3_min = min(t3_min, t3)
        
        # Update t4 tracking
        t4_max = max(t4_max, t4)
        t4_min = min(t4_min, t4)
    
    # Compute the maximum differences for all transformations
    result = max(t1_max - t1_min, t2_max - t2_min, t3_max - t3_min, t4_max - t4_min)
    return result

# Example usage:
print(maxAbsValExpr([1, 2, 3, 4], [-1, 4, 5, 6]))  # Expected output: 13