Scale Engineer

Maximum of Absolute Value Expression

Med
#1067Time: O(n^2), where n is the length of the arrays. The nested loops result in n*n iterations.Space: O(1), as we only use a few variables to store the intermediate and final results, regardless of the input size.
Patterns
Math
Data structures
Array

Prompt

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.

 

Example 1:

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

Example 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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly implements the problem statement by checking every possible pair of indices (i, j). It uses nested loops to iterate through all combinations and calculates the value of the expression |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j| for each pair. The maximum value found during this process is stored and returned as the result.

Algorithm

  • Initialize a variable maxVal to 0.
  • Get the length of the arrays, n.
  • Use a nested loop to iterate through all pairs of indices (i, j) from 0 to n-1.
  • For each pair (i, j), calculate the value currentVal = |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|.
  • Update maxVal = max(maxVal, currentVal).
  • After the loops complete, return maxVal.

Walkthrough

The brute-force method is the most straightforward way to solve the problem. It considers every single pair of indices (i, j) and computes the expression's value. By keeping track of the largest value seen so far, we can find the overall maximum. While simple, its performance degrades quadratically with the size of the input arrays, making it unsuitable for the given constraints.

class Solution {    public int maxAbsValExpr(int[] arr1, int[] arr2) {        int n = arr1.length;        int maxVal = 0;        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                int val = Math.abs(arr1[i] - arr1[j]) +                           Math.abs(arr2[i] - arr2[j]) +                           Math.abs(i - j);                if (val > maxVal) {                    maxVal = val;                }            }        }        return maxVal;    }}

Complexity

Time

O(n^2), where n is the length of the arrays. The nested loops result in n*n iterations.

Space

O(1), as we only use a few variables to store the intermediate and final results, regardless of the input size.

Trade-offs

Pros

  • Simple to understand and implement.

  • Directly follows the problem definition.

Cons

  • Inefficient for large inputs. With n up to 40000, this will lead to a "Time Limit Exceeded" error.

Solutions

class Solution {public  int maxAbsValExpr(int[] arr1, int[] arr2) {    int[] dirs = {1, -1, -1, 1, 1};    final int inf = 1 << 30;    int ans = -inf;    int n = arr1.length;    for (int k = 0; k < 4; ++k) {      int a = dirs[k], b = dirs[k + 1];      int mx = -inf, mi = inf;      for (int i = 0; i < n; ++i) {        mx = Math.max(mx, a * arr1[i] + b * arr2[i] + i);        mi = Math.min(mi, a * arr1[i] + b * arr2[i] + i);        ans = Math.max(ans, mx - mi);      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem