Maximum Absolute Value Expression

Array Math

Problem

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.

For example:

Input: arr1 = [1,2,3,4], 
       arr2 = [-1,4,5,6]
Output: 13

Input: arr1 = [1,-2,-5,0,10], 
       arr2 = [0,-2,-1,-7,-4]
Output: 20

Thought Process

Since we have three absolute value signs (| |), for each one we have 2 options, so overall we have 8 potential options. However, realize the indexes (i and j) do not matter ; no matter if its index i or index j, it just represents an index that's shared by both arr1 and arr2, and whether index i or index j is greater than the other. The index j can be replaced by i and vice versa for half of the fomulas. This means we can generalize to 4 formulas.

• $(arr1[i] + arr2[i] + i) - (arr1[j] + arr2[j] + j)$

• $(arr1[i] + arr2[i] - i) - (arr1[j] + arr2[j] - j)$

• $(arr1[i] - arr2[i] + i) - (arr1[j] - arr2[j] + j)$

• $(arr1[i] - arr2[i] - i) - (arr1[j] - arr2[j] - j)$

To find the maximum of absoulte value, we need to find the maximum of the left hand side of the formula subracted by the minimum of the right hand side of the formula.

Solution

class Solution:
    def findMaxMin(self,sign1,sign2,array1,array2):
        maxNum = float("-inf")
        minNum = float("inf")
        
    
        for i in range(len(array1)):
            formula = sign1*array1[i] + sign2*array2[i] + i
            maxNum = max(maxNum, formula)
            minNum = min(minNum, formula)
        
        return maxNum-minNum
        
    
    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
        maxAbs = 0
        
        maxAbs = max(maxAbs, self.findMaxMin(1,1,arr1,arr2))
        maxAbs = max(maxAbs, self.findMaxMin(-1,1,arr1,arr2))
        maxAbs = max(maxAbs, self.findMaxMin(1,-1,arr1,arr2))
        maxAbs = max(maxAbs, self.findMaxMin(-1,-1,arr1,arr2))

        return maxAbs

Key Facts

• With absolute value, there are two potential choices. With three absolute value signs, we have 8 potential choices, but these 8 choices can be generalized to 4 choices when we can think of the indexes (i and j) being interchangable for formulas that essentially make two formulas the same. For example, take formula 1 (top left of picture) and formula 8 (bottom right). In formula 1, index i is greater than j (meaning the index is greater) and array1[i] is greater than array1[j], and array2[i] is greater than array2[j]. Now, in formula 8, index j is greater than i (meaning the index is greater) and array1[j] is greater than array1[i], and array2[j] is greater than array2[i]. Both formulas 1 and 8 are the same, as we can see in both that one index is greater than the other and for the corressponding array1 and array2 mapped to those indexes. For both formulas we are saying, "one index is greater than the other, element at array1[i] is greater than element at array1[j], and element at array2[i] is greater than element at array2[j]." The indexes (i and j) for formula 1 can be interchangable with the indexes in formula 8 and it will still be the same formula. The same goes for the other 6 formulas mapped to one another.

Time Complexity

• Time: $O(n)$

• Space: $O(1)$