Maximum of Absolute Value Expression - Practice Coding Problems

Maximum of Absolute Value Expression - Problem

Array Math Medium

Given two arrays of integers arr1 and arr2 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.

Input & Output

Example 1 — Basic Case

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

› Output: 13

💡 Note: Maximum occurs at i=3, j=0: |4-1| + |6-(-1)| + |3-0| = 3 + 7 + 3 = 13

Example 2 — Small Array

$ Input: arr1 = [1,-2], arr2 = [-1,4]

› Output: 9

💡 Note: Only two elements: |1-(-2)| + |-1-4| + |0-1| = 3 + 5 + 1 = 9

Example 3 — Same Values

$ Input: arr1 = [1,1,1], arr2 = [2,2,2]

› Output: 2

💡 Note: Arrays have same values, maximum comes from index difference: |1-1| + |2-2| + |0-2| = 0 + 0 + 2 = 2

Constraints

2 ≤ arr1.length == arr2.length ≤ 40000
-10⁶ ≤ arr1[i], arr2[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Two arrays of equal length

Expression

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

Maximum

Find the maximum value over all pairs

Key Takeaway

🎯 Key Insight: Transform absolute value expressions into linear cases to avoid checking all pairs

Asked in

G Google 25 f Facebook 18 a Amazon 12

The key insight is transforming the complex absolute value expression into linear cases. The optimal approach uses mathematical optimization to expand |a| + |b| + |c| into 4 cases, then finds max-min for each case in O(n) time. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	Check all pairs of indices and compute the expression value
Mathematical Optimization	O(n)	O(1)	Transform absolute value expressions to eliminate nested loops

Brute Force — Algorithm Steps

Iterate through all pairs (i,j)
Calculate expression for each pair
Keep track of maximum value

Visualization

Tap to expand

Step-by-Step Walkthrough

Input Arrays

Two arrays with equal length

Check Pairs

Calculate expression for each (i,j) pair

Find Maximum

Track the highest value found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int abs_val(int x) {
    return x < 0 ? -x : x;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int solution(int* arr1, int* arr2, int n) {
    int maxVal = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int val = abs_val(arr1[i] - arr1[j]) + abs_val(arr2[i] - arr2[j]) + abs_val(i - j);
            maxVal = max(maxVal, val);
        }
    }
    
    return maxVal;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int arr1[100], arr2[100];
    int n1 = 0, n2 = 0;
    
    // Parse first array
    char* token = strtok(line, "[,]");
    while (token != NULL && n1 < 100) {
        arr1[n1++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]");
    while (token != NULL && n2 < 100) {
        arr2[n2++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(arr1, arr2, n1));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops iterate through all n² pairs of indices

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables to track maximum

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler