Domain 2MediumMEDIUM

Maximum of Absolute Value Expression

Given two arrays, find the maximum Manhattan distance-like expression by expanding absolute values into 8 linear sign combinations and tracking min/max in a single pass per combination.

Domain: medium•Updated: 2026-09-09
#math#linear scan#O(N)#absolute value

Problem Breakdown

We are given two integer arrays arr1 and arr2, both of equal length NN. We need to find the maximum value of the expression for any pair of indices (i,j)(i, j) where 0≤i,j<N0 \le i, j < N: ∣arr1[i]−arr1[j]∣+∣arr2[i]−arr2[j]∣+∣i−j∣|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|

Inputs: Two arrays arr1, arr2 with length NN.
Output: A single integer representing the maximum value.

Constraints & Edge Cases:

  • Length (NN): Up to 40,000. This rules out an O(N2)O(N^2) brute-force solution (which would be ≈1.6×109\approx 1.6 \times 10^9 operations). We need something closer to linear time.
  • Values: Integers between −106-10^6 and 10610^6. Python handles large integers automatically, so overflow is not a concern like in C++/Java.
  • Indices: The term ∣i−j∣|i - j| treats the index itself as a value to be maximized/differenced alongside array values. This effectively transforms this into a 3D Manhattan distance problem where one dimension is time/index and two are spatial coordinates from arr1 and arr2.

Intuition

A brute-force approach iterates all pairs (i,j)(i, j) in O(N2)O(N^2). Given the constraint of N=40,000N=40,000, this will exceed typical execution limits (usually ∼108\sim 10^8 operations per second). We need an optimization.

The expression consists of three absolute value terms: ∣Ai−Aj∣+∣Bi−Bj∣+∣Ii−Ij∣|A_i - A_j| + |B_i - B_j| + |I_i - I_j| Recall that ∣x∣|x| is equivalent to either (+x)(+x) or (−x)(-x). Therefore, each term can be expanded into two possibilities. With three independent absolute value terms, there are 23=82^3 = 8 possible sign combinations for the entire expression relative to a specific pair order (e.g., we might have (Ai−Aj)(A_i - A_j) vs (Aj−Ai)(A_j - A_i)).

For any fixed combination of signs (say all positive), the expression becomes linear: s1(arr1[i]−arr1[j])+s2(arr2[i]−arr2[j])+s3(i−j)s_1(arr1[i] - arr1[j]) + s_2(arr2[i] - arr2[j]) + s_3(i - j) Rearranging terms by index kk: (s1⋅arr1[k]+s2⋅arr2[k]+s3⋅k)at i−(s1⋅arr1[k]+s2⋅arr2[k]+s3⋅k)at j(s_1 \cdot arr1[k] + s_2 \cdot arr2[k] + s_3 \cdot k)_{\text{at } i} - (s_1 \cdot arr1[k] + s_2 \cdot arr2[k] + s_3 \cdot k)_{\text{at } j} This simplifies to finding the maximum difference between a transformed value at index ii and a transformed value at index jj. The max difference for any linear combination is simply (max⁡(transformed))−(min⁡(transformed))(\max(\text{transformed})) - (\min(\text{transformed})).

Since we want the global maximum over all pairs, we iterate through all 8 sign combinations. For each combination, we compute the transformed values across the array and find their range (Max - Min). The overall answer is the largest of these ranges found across all 8 cases. This reduces complexity to O(N)O(N).

Approach

  1. Initialize a global max_result variable to negative infinity.
  2. Define the three variables involved in absolute differences: values from arr1, arr2, and their indices (00 to N−1N-1).
  3. Iterate through all 8 possible sign combinations for these three terms (using coefficients ±1\pm 1).
  4. For each combination, define a linear function f(k)=s1⋅arr1[k]+s2⋅arr2[k]+s3⋅kf(k) = s_1 \cdot arr1[k] + s_2 \cdot arr2[k] + s_3 \cdot k.
  5. Traverse the array once per sign combination to find min_f and max_f.
  6. Update max_result with max_f−min_f\text{max\_f} - \text{min\_f} for that specific combination.
  7. Return max_result.

Complexity Analysis

  • Time Complexity: O(N)O(N). We iterate through the array 8 times (constant factor), so it remains linear relative to input size NN. With N=40,000N=40,000, this is well within limits.
  • Space Complexity: O(1)O(1) auxiliary space. We only store a few variables for min/max tracking per iteration and do not allocate new arrays proportional to NN (though Python’s list access overhead exists implicitly).

Solution

import itertools

def maximumOfAbsoluteValueExpression(arr1, arr2):
    """
    Calculates the maximum value of |arr1[i] - arr1[j]| + 
    |arr2[i] - arr2[j]| + |i - j| using a linear scan approach.
    
    Args:
        arr1 (List[int]): First array of integers.
        arr2 (List[int]): Second array of integers, same length as arr1.
        
    Returns:
        int: The maximum value found across all valid pairs (i, j).
    """
    n = len(arr1)
    
    # Initialize global max result to a very small number
    ans = float('-inf')

    # Iterate over all 8 combinations of signs for the three terms.
    # Each term corresponds to: arr1[i], arr2[i], and index i.
    # We want to maximize (s1*arr1 + s2*arr2 + s3*i) - (same at j).
    # This is equivalent to finding max_val - min_val for each sign combo.
    
    # itertools.product([-1, 1], repeat=3) generates tuples like (-1,-1,-1), etc.
    for s1, s2, s3 in itertools.product([-1, 1], repeat=3):
        
        current_min = float('inf')
        current_max = float('-inf')

        # Single pass to find min and max of the transformed value for this sign combo
        for k in range(n):
            val = s1 * arr1[k] + s2 * arr2[k] + s3 * k
            
            if val < current_min:
                current_min = val
            elif val > current_max:
                current_max = val
        
        # The max difference for this specific sign configuration is (max - min)
        diff = current_max - current_min
        
        # Update the global answer with the maximum difference found so far
        if diff > ans:
            ans = diff
            
    return int(ans)

Edge Cases Handled

  • Negative Values: The logic handles negative integers in arr1 and arr2 correctly because Python’s integer arithmetic supports arbitrary precision, and the sign expansion covers all relative orderings.
  • Large N (40k): The O(N)O(N) approach ensures execution time remains low despite large input size.
  • Index Differences: By treating index ii as a value multiplied by coefficient ±1\pm 1, we correctly account for the ∣i−j∣|i - j| term in all possible relative orderings of indices (e.g., when i>ji > j vs j>ij > i).