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
:
arr1[i] - arr2[i] + i
-arr1[i] - arr2[i] + i
-arr1[i] + arr2[i] + i
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 EvaluatorExample 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
andj = 1
:- The expression would be
|1 - 2| + |4 - 5| + |0 - 1| = 1 + 1 + 1 = 3
- The expression would be
- For
i = 0
andj = 2
:- The expression would be
|1 - 3| + |4 - 6| + |0 - 2| = 2 + 2 + 2 = 6
- The expression would be
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:
- We will consider four cases by applying the
pairwise
concept to thedirs
tuple.- We don't actually need the
pairwise
function here because we know our cases in advance:
- We don't actually need the
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
-
We will iterate over each element
i
ofarr1
andarr2
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 rangemx - mi
in each case which is a potential maximum for our final answer. -
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 rangemx - mi
is-1 - (-3) = 2
- For
-
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 rangemx - mi
is-5 - (-7) = 2
- For
-
Proceed similarly for Case 3 and Case 4, updating
mx
andmi
for each case, then compute the rangemx - mi
to see if the result is higher than the previous cases. -
After evaluating all four cases, the final answer
ans
would be the maximum rangemx - 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
andarr2
simultaneously, usingenumerate(zip(arr1, arr2))
, which runs forn
iterations wheren
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 toO(n)
.
- There are 4 pairs of
-
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
, andi
), regardless of the input size. - As such, the space complexity is
O(1)
.
- The additional space used by the algorithm is constant. It only needs a few variables for tracking maximum values, minimum values, and indices (
Learn more about how to find time and space complexity quickly using problem constraints.
How does merge sort divide the problem into subproblems?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
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.