1131. Maximum of Absolute Value Expression


Problem Description

Given two integer arrays arr1 and arr2 of the same length, the task is to calculate the maximum value of a specific expression for all pairs of indices (i, j) where 0 <= i, j < arr1.length. The expression to maximize is:

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

The | | denotes the absolute value, and the goal is to find the maximum result possible by choosing different values of i and j.

Intuition

The intuitive approach to this problem would be to consider all possible pairs of indices (i, j) and calculate the value of the expression for each pair, but this would lead to a rather inefficient solution with a quadratic runtime complexity. To optimize this, one must find a smarter way to ascertain the maximum value without directly examining every pair.

The important realization is that the expression can be rewritten and analyzed in terms of its components. Notice that the expression comprises three terms: the absolute difference between arr1 elements, the absolute difference between arr2 elements, and the absolute difference between indices.

We can reformulate each term like this:

1|arr1[i] - arr1[j]| can be either (arr1[i] - arr1[j]) or -(arr1[i] - arr1[j])
2|arr2[i] - arr2[j]| can be either (arr2[i] - arr2[j]) or -(arr2[i] - arr2[j])
3|i - j| can be either (i - j) or -(i - j)

Each of these can have two possible signs (+ or -), which gives us a total of 2 * 2 * 2 = 8 combinations. Each combination can be thought of representing a different "direction" or case. However, for this solution, we take into account that |i - j| is always added to the expression, thus we only need to consider four combinations for the terms from the arrays arr1 and arr2.

The code uses a pairwise function in combination with a dirs tuple to go through these four combinations (-1 and 1 represent the possible signs). For each case, it initializes minimum (mi) and maximum (mx) values that could be yielded by the expression when evaluating for all indices (i, j). At each step in the loop, the code updates the mx and mi to find the maximum possible value for the current combination and eventually computes the maximum possible value for the overall expression by comparing it against the maximum (ans) of previous cases.

Thus, instead of comparing all pairs of (i, j), we keep track of the max and min value of a * arr1[i] + b * arr2[i] + i for each direction and use these values to calculate and update the running maximum value over the entire array.

Learn more about Math patterns.

Solution Approach

The solution utilizes the fact that every absolute difference between two numbers can be represented as either a positive or a negative difference. Therefore, for each element in the arrays, we can apply either a positive or a negative sign, leading to different cases. The goal is to calculate the maximum value of our expression within each of these cases.

Since we have two arrays and we need to consider positive and negative contributions of their elements independently, we need to evaluate four cases. The dirs tuple (1, -1, -1, 1) along with pairwise is used to iterate over these cases. The pairwise function is not built into Python, but it would simply return pairs of elements from dirs, e.g., (1, -1), (-1, -1), (-1, 1). This means we evaluate the following cases for each index i:

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

For each of the four cases, we use a loop to iterate over all indices i of our input arrays.

Within each loop iteration, we apply the current case's signs to elements of arr1[i] and arr2[i] and add the index i. We update mx to be the maximum value seen so far and mi to be the minimum value seen so far.

1mx = max(mx, a * arr1[i] + b * arr2[i] + i)
2mi = min(mi, a * arr1[i] + b * arr2[i] + i)

The maximum value for this case is then mx - mi, which represents the widest range we've seen between the expression values for any pair of indices within this particular case.

ans = max(ans, mx - mi)

This line updates the overall maximum value ans with the maximum value obtained in the current case. By the end of the for-loop that iterates over the pairwise elements, we've considered all possible signs for differences and added the absolute difference of indices, yielding the maximum value of the original expression.

Finally, we return ans, which represents the maximum value of the expression across all pairs (i, j).

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with an example. Suppose we have the following arrays:

1arr1 = [1, 2, 3]
2arr2 = [4, 5, 6]

For these arrays, we want to maximize the expression:

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

First, let's manually calculate the expression for some pairs to understand the problem:

  • For i = 0 and j = 1:
    • The expression would be |1 - 2| + |4 - 5| + |0 - 1| = 1 + 1 + 1 = 3
  • For i = 0 and j = 2:
    • The expression would be |1 - 3| + |4 - 6| + |0 - 2| = 2 + 2 + 2 = 6

We notice that as i and j get farther apart, the expression tends to increase because of the |i - j| term, but the first two absolute terms can also impact the result.

Let's now use the optimized approach described in the solution:

  1. We will consider four cases by applying the pairwise concept to the dirs tuple.
    • We don't actually need the pairwise function here because we know our cases in advance:
1Case 1: arr1[i] - arr2[i] + i
2Case 2: -arr1[i] - arr2[i] + i
3Case 3: -arr1[i] + arr2[i] + i
4Case 4: arr1[i] + arr2[i] + i
  1. We will iterate over each element i of arr1 and arr2 and calculate the expressions for each of the four cases, updating the maximum (mx) and minimum (mi) as we go. We then use these to compute the range mx - mi in each case which is a potential maximum for our final answer.

  2. Let's start with Case 1 (arr1[i] - arr2[i] + i)

    • For i = 0: 1 - 4 + 0 = -3
    • For i = 1: 2 - 5 + 1 = -2
    • For i = 2: 3 - 6 + 2 = -1
    • mx of Case 1 is -1, mi is -3, and the range mx - mi is -1 - (-3) = 2
  3. Next is Case 2 (-arr1[i] - arr2[i] + i)

    • For i = 0: -1 - 4 + 0 = -5
    • For i = 1: -2 - 5 + 1 = -6
    • For i = 2: -3 - 6 + 2 = -7
    • mx of Case 2 is -5, mi is -7, the range mx - mi is -5 - (-7) = 2
  4. Proceed similarly for Case 3 and Case 4, updating mx and mi for each case, then compute the range mx - mi to see if the result is higher than the previous cases.

  5. After evaluating all four cases, the final answer ans would be the maximum range mx - mi found among all cases.

For our example, the ranges were the same (2) for Case 1 and Case 2, and if we calculate it for Cases 3 and 4, we would get 10 and 8 respectively. Hence, the maximum value for the expression |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j| across all i, j with 0 <= i, j < arr1.length would be 10.

This example shows how to compute the maximum value effectively without checking each combination of i and j individually. By considering the varied outcomes of applying both the positive and negative signs, we manage to find the optimal result with a more efficient approach.

Solution Implementation

1from itertools import product
2from math import inf
3
4class Solution:
5    def maxAbsValExpr(self, arr1, arr2):
6        # Initialize maximum absolute value expression to a very small number
7        max_absolute_value_expr = -inf
8      
9        # Iterate over all combinations of directions for arr1 and arr2.
10        # Each combination represents multiplying arr1 and arr2 with
11        # 1 or -1, effectively checking all possible cases.
12        for dir1, dir2 in product((1, -1), repeat=2):
13            # Initialize maximum and minimum values observed 
14            # for the current direction combination
15            max_val, min_val = -inf, inf
16          
17            # Iterate over the pairs (i, (x, y)) where i is the index, 
18            # x is the element from arr1, and y is the element from arr2
19            for i, (x, y) in enumerate(zip(arr1, arr2)):
20                # Calculate the current value using the expression given by the problem
21                current_value = dir1 * x + dir2 * y + i
22              
23                # Update the maximum and minimum observed values
24                max_val = max(max_val, current_value)
25                min_val = min(min_val, current_value)
26          
27            # Update the maximum absolute value expression with the 
28            # maximum difference between observed values
29            max_absolute_value_expr = max(max_absolute_value_expr, max_val - min_val)
30      
31        # Return the maximum absolute value expression found
32        return max_absolute_value_expr
33
1class Solution {
2    public int maxAbsValExpr(int[] arr1, int[] arr2) {
3        // Define the multipliers to represent the four possible combinations 
4        // of adding or subtracting arr1[i] and arr2[i]. 
5        // These multipliers will be applied inside the loop below.
6        int[] multipliers = {1, -1, -1, 1};
7      
8        // Initialize variable 'maxDifference' to keep track of the maximum absolute value 
9        // expression found. This value will be returned at the end.
10        // Using Integer.MIN_VALUE to handle negative overflow edge case.
11        int maxDifference = Integer.MIN_VALUE;
12
13        // Length of the given arrays, assuming both arrays have the same length.
14        int n = arr1.length;
15
16        // Iterate over the four possible combinations of expressions represented by multipliers.
17        for (int k = 0; k < 4; ++k) {
18            // Variables representing the direction for arr1[i] and arr2[i] 
19            // in the expression based on the current multiplier.
20            int a = multipliers[k], b = multipliers[k + 1];
21
22            // Initialize 'maxValue' and 'minValue' to track the maximum and minimum values
23            // of the expression for a given set of multipliers.
24            // Using Integer.MIN_VALUE and Integer.MAX_VALUE to start with the extreme possible values.
25            int maxValue = Integer.MIN_VALUE, minValue = Integer.MAX_VALUE;
26
27            // Iterate through the elements of the arrays to calculate the expressions.
28            for (int i = 0; i < n; ++i) {
29                // Calculate the current value of the expression.
30                int currentValue = a * arr1[i] + b * arr2[i] + i;
31
32                // Update 'maxValue' and 'minValue' if the current value is greater than 'maxValue'
33                // or less than 'minValue' respectively.
34                maxValue = Math.max(maxValue, currentValue);
35                minValue = Math.min(minValue, currentValue);
36
37                // Update 'maxDifference' with the maximum difference found so far.
38                maxDifference = Math.max(maxDifference, maxValue - minValue);
39            }
40        }
41      
42        // Return the maximum absolute value expression found.
43        return maxDifference;
44    }
45}
46
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7    int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) {
8        // Directions are the coefficients for arr1 and arr2 in the combinations
9        // Last element is duplicated for easy loop termination
10        int directions[5] = {1, -1, -1, 1, 1};
11        const int INF = 1 << 30; // Define infinity as a large number
12        int maxAnswer = -INF; // Initialize the maximum answer to negative infinity
13        int arraySize = arr1.size(); // Get the size of the input arrays
14      
15        // Iterate over the 4 combinations of signs in the expression
16        for (int k = 0; k < 4; ++k) {
17            int coefficientA = directions[k], // Coefficient for arr1
18                coefficientB = directions[k + 1]; // Coefficient for arr2
19            int maxExprValue = -INF, // Initialize max expression value in the current loop
20                minExprValue = INF;  // Initialize min expression value in the current loop
21          
22            // Loop through each element in the array to find max and min of expression
23            for (int i = 0; i < arraySize; ++i) {
24                // Find the maximum value expression with the current coefficients
25                maxExprValue = max(maxExprValue, coefficientA * arr1[i] + coefficientB * arr2[i] + i);
26                // Find the minimum value expression with the current coefficients
27                minExprValue = min(minExprValue, coefficientA * arr1[i] + coefficientB * arr2[i] + i);
28                // Update the overall maximum answer with the difference between max and min
29                maxAnswer = max(maxAnswer, maxExprValue - minExprValue);
30            }
31        }
32        return maxAnswer; // Return the found maximum absolute value of an expression
33    }
34};
35
1// Calculates the maximum absolute value expression for two arrays
2function maxAbsValExpr(arr1: number[], arr2: number[]): number {
3    // Define multipliers for different expression scenarios
4    const multipliers = [1, -1, -1, 1, 1];
5  
6    // Initialize the maximum answer as the smallest integer possible
7    let maxAnswer = Number.MIN_SAFE_INTEGER;
8
9    // Iterate through all possible expressions based on multipliers
10    for (let expIndex = 0; expIndex < 4; ++expIndex) {
11        // Select multipliers for current expression
12        const coeffA = multipliers[expIndex];
13        const coeffB = multipliers[expIndex + 1];
14
15        // Initialize max and min variables for current expression scenario
16        let maxCurrent = Number.MIN_SAFE_INTEGER;
17        let minCurrent = Number.MAX_SAFE_INTEGER;
18
19        // Iterate through elements of the arrays to compute expressions
20        for (let i = 0; i < arr1.length; ++i) {
21            const val1 = arr1[i];
22            const val2 = arr2[i];
23
24            // Calculate the expression value with current i
25            const expression = coeffA * val1 + coeffB * val2 + i;
26
27            // Update the current maximum and minimum
28            maxCurrent = Math.max(maxCurrent, expression);
29            minCurrent = Math.min(minCurrent, expression);
30
31            // Update the global maximum answer
32            maxAnswer = Math.max(maxAnswer, maxCurrent - minCurrent);
33        }
34    }
35  
36    // Return the calculated maximum absolute value expression
37    return maxAnswer;
38}
39

Time and Space Complexity

The given Python code calculates the maximum absolute value expression for two arrays arr1 and arr2.

  • Time Complexity:

    • There are 4 pairs of (a, b) which correspond to each combination of {1, -1} for each array element.
    • For each of these 4 pairs, we iterate through both arr1 and arr2 simultaneously, using enumerate(zip(arr1, arr2)), which runs for n iterations where n is the length of the input arrays.
    • Inside the loop, we perform constant-time operations such as comparisons and arithmetic operations.
    • Therefore, the time complexity is O(4n) which simplifies to O(n).
  • Space Complexity:

    • The additional space used by the algorithm is constant. It only needs a few variables for tracking maximum values, minimum values, and indices (mx, mi, and i), regardless of the input size.
    • As such, the space complexity is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

How does merge sort divide the problem into subproblems?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.