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.

Examples

Example 1

1
2

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

Example 2

1
2

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

Constraints

  • 2 <= arr1.length == arr2.length <= 40000
  • -10^6 <= arr1[i], arr2[i] <= 10^6

Solution

Method 1 – Enumerate All Sign Combinations

Intuition

The given expression can be rewritten by considering all possible sign combinations for the absolute values. For each combination, the expression reduces to a linear form, and the answer is the maximum difference for each form.

Approach

  1. For each of the four sign combinations (+/-, +/-), compute the value for each index:
    • val = s1 * arr1[i] + s2 * arr2[i] + i
    • where s1, s2 are either +1 or -1.
  2. For each combination, track the minimum and maximum value across all indices.
  3. The answer is the maximum difference among all combinations.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) {
        int n = arr1.size(), ans = 0;
        for (int s1 : {1, -1}) {
            for (int s2 : {1, -1}) {
                int mx = INT_MIN, mn = INT_MAX;
                for (int i = 0; i < n; ++i) {
                    int val = s1 * arr1[i] + s2 * arr2[i] + i;
                    mx = max(mx, val);
                    mn = min(mn, val);
                }
                ans = max(ans, mx - mn);
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func maxAbsValExpr(arr1 []int, arr2 []int) int {
    n, ans := len(arr1), 0
    signs := [2]int{1, -1}
    for _, s1 := range signs {
        for _, s2 := range signs {
            mx, mn := math.MinInt32, math.MaxInt32
            for i := 0; i < n; i++ {
                val := s1*arr1[i] + s2*arr2[i] + i
                if val > mx {
                    mx = val
                }
                if val < mn {
                    mn = val
                }
            }
            if mx-mn > ans {
                ans = mx - mn
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    public int maxAbsValExpr(int[] arr1, int[] arr2) {
        int n = arr1.length, ans = 0;
        int[] signs = {1, -1};
        for (int s1 : signs) {
            for (int s2 : signs) {
                int mx = Integer.MIN_VALUE, mn = Integer.MAX_VALUE;
                for (int i = 0; i < n; i++) {
                    int val = s1 * arr1[i] + s2 * arr2[i] + i;
                    mx = Math.max(mx, val);
                    mn = Math.min(mn, val);
                }
                ans = Math.max(ans, mx - mn);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun maxAbsValExpr(arr1: IntArray, arr2: IntArray): Int {
        val n = arr1.size
        var ans = 0
        val signs = listOf(1, -1)
        for (s1 in signs) {
            for (s2 in signs) {
                var mx = Int.MIN_VALUE
                var mn = Int.MAX_VALUE
                for (i in 0 until n) {
                    val v = s1 * arr1[i] + s2 * arr2[i] + i
                    mx = maxOf(mx, v)
                    mn = minOf(mn, v)
                }
                ans = maxOf(ans, mx - mn)
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def maxAbsValExpr(self, arr1: list[int], arr2: list[int]) -> int:
        n = len(arr1)
        ans = 0
        for s1 in [1, -1]:
            for s2 in [1, -1]:
                mx, mn = float('-inf'), float('inf')
                for i in range(n):
                    v = s1 * arr1[i] + s2 * arr2[i] + i
                    mx = max(mx, v)
                    mn = min(mn, v)
                ans = max(ans, mx - mn)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

impl Solution {
    pub fn max_abs_val_expr(arr1: Vec<i32>, arr2: Vec<i32>) -> i32 {
        let n = arr1.len();
        let mut ans = 0;
        for &s1 in &[1, -1] {
            for &s2 in &[1, -1] {
                let mut mx = i32::MIN;
                let mut mn = i32::MAX;
                for i in 0..n {
                    let v = s1 * arr1[i] + s2 * arr2[i] + i as i32;
                    mx = mx.max(v);
                    mn = mn.min(v);
                }
                ans = ans.max(mx - mn);
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    maxAbsValExpr(arr1: number[], arr2: number[]): number {
        let ans = 0, n = arr1.length;
        for (const s1 of [1, -1]) {
            for (const s2 of [1, -1]) {
                let mx = -Infinity, mn = Infinity;
                for (let i = 0; i < n; i++) {
                    const v = s1 * arr1[i] + s2 * arr2[i] + i;
                    mx = Math.max(mx, v);
                    mn = Math.min(mn, v);
                }
                ans = Math.max(ans, mx - mn);
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We scan the arrays four times.
  • 🧺 Space complexity: O(1) — Only a few variables are used.