Maximum Of Absolute Value Expression - Leetcode Solution

Problem Statement:

Given two arrays of integers with equal lengths, find the maximum value of:

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

where 0 <= i < j < arr1.length.

Solution:

To solve this problem, we’ll decompose the given expression into four parts:

• |arr1[i] - arr1[j]|: This part is equivalent to finding the maximum difference between any two elements in the array arr1.
• |arr2[i] - arr2[j]|: This part is equivalent to finding the maximum difference between any two elements in the array arr2.
• |i - j|: This part is equivalent to finding the maximum difference between any two indices i and j (with i < j).
• The sum of the three above parts.

Let’s start by solving the first two parts:

1. To find the maximum difference between any two elements in arr1, we can simply find the minimum and maximum elements and take their difference. This can be done in O(n) time complexity.

   max1 = max(arr1)

   min1 = min(arr1)

   max_diff1 = max1 - min1

2. Similarly, to find the maximum difference between any two elements in arr2, we can simply find the minimum and maximum elements and take their difference. This can also be done in O(n) time complexity.

   max2 = max(arr2)

   min2 = min(arr2)

   max_diff2 = max2 - min2

Now let’s solve the third part:

3. To find the maximum difference between any two indices i and j (with i < j), we can simply take the absolute difference between the size of the array and subtract it from 1. This is because the maximum difference between two indices must be equal to the size of the array minus 1.

   max_diff3 = len(arr1) - 1

Now let’s combine these three parts:

max_value = max_diff1 + max_diff2 + max_diff3

This will give us the maximum value of the given expression. However, we need to make sure that we consider pairs (i, j) that satisfy the condition 0 <= i < j < arr1.length.

We can generate all such pairs using two nested loops and update the maximum value accordingly:

max_value = 0

for i in range(len(arr1)):

     for j in range(i+1, len(arr1)):
     
           value = abs(arr1[i] - arr1[j]) + abs(arr2[i] - arr2[j]) + abs(i - j)
           
           max_value = max(max_value, value)

Finally, we return the max_value obtained as the maximum of the given expression.

Time and Space Complexity:

The time complexity of the solution is O(n^2) because we are using two nested loops to check all possible pairs of indices.

The space complexity of the solution is O(1) because we are not using any extra space apart from the input arrays.

1