Maximum Distance in Arrays - Practice Coding Problems

Maximum Distance in Arrays - Problem

Array Greedy Medium

You are given m arrays, where each array is sorted in ascending order. You can pick up two integers from two different arrays (each array picks one) and calculate the distance. We define the distance between two integers a and b to be their absolute difference |a - b|.

Return the maximum distance.

Input & Output

Example 1 — Basic Case

$ Input: arrays = [[1,2,3],[4,5],[1,2,3]]

› Output: 4

💡 Note: One way to reach the maximum distance 4 is to pick 1 in the first or third array and pick 5 in the second array.

Example 2 — Different Arrays

$ Input: arrays = [[1],[1]]

› Output: 0

💡 Note: Both arrays contain only 1, so the maximum distance is |1-1| = 0.

Example 3 — Negative Numbers

$ Input: arrays = [[-1,1],[-3,1,4],[-2,-1,0,2]]

› Output: 7

💡 Note: Maximum distance is achieved by picking -3 from second array and 4 from second array... wait, they must be from different arrays. Pick -3 from second array and 4 from third array gives |4-(-3)| = 7.

Constraints

m == arrays.length
2 ≤ m ≤ 10⁵
1 ≤ arrays[i].length ≤ 500
-10⁴ ≤ arrays[i][j] ≤ 10⁴
arrays[i] is sorted in ascending order.

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Multiple sorted arrays with different ranges

Find Extremes

Identify minimum and maximum values across arrays

Calculate Distance

Maximum distance is between global min and max from different arrays

Key Takeaway

🎯 Key Insight: Maximum distance always comes from pairing extreme values from different arrays

Asked in

G Google 15 a Amazon 12 Apple 8

The key insight is that maximum distance always comes from pairing extreme values (min and max) from different arrays. Since arrays are sorted, we only need to compare the first and last elements. Best approach uses min-max optimization tracking global extremes. Time: O(m), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	Compare every element from every array with every other array
Min-Max Optimization	O(m)	O(1)	Only compare minimum and maximum values from each array

Brute Force — Algorithm Steps

Iterate through each array
For each element, compare with all elements in other arrays
Track maximum distance found

Visualization

Tap to expand

Step-by-Step Walkthrough

Compare Arrays

Check each element in array 1 vs array 2

Find Distances

Calculate |a - b| for all pairs

Track Maximum

Keep the largest distance 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** arrays, int* arraySizes, int arrayCount) {
    int maxDistance = 0;
    
    for (int i = 0; i < arrayCount; i++) {
        for (int j = 0; j < arrayCount; j++) {
            if (i != j) {
                for (int x = 0; x < arraySizes[i]; x++) {
                    for (int y = 0; y < arraySizes[j]; y++) {
                        maxDistance = max(maxDistance, abs_val(arrays[i][x] - arrays[j][y]));
                    }
                }
            }
        }
    }
    
    return maxDistance;
}

int main() {
    char input[10000];
    fgets(input, sizeof(input), stdin);
    input[strcspn(input, "\n")] = 0;
    
    // Simple parsing for demo - assumes format [[1,2],[3,4]]
    int** arrays = malloc(100 * sizeof(int*));
    int* arraySizes = malloc(100 * sizeof(int));
    int arrayCount = 0;
    
    // Basic parsing logic would go here
    // For demo purposes, create sample data
    arrays[0] = malloc(2 * sizeof(int));
    arrays[0][0] = 1; arrays[0][1] = 2;
    arraySizes[0] = 2;
    arrays[1] = malloc(2 * sizeof(int));
    arrays[1][0] = 3; arrays[1][1] = 4;
    arraySizes[1] = 2;
    arrayCount = 2;
    
    int result = solution(arrays, arraySizes, arrayCount);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each element in all arrays, we check against all elements in other arrays

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track maximum distance

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 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