LeetCode 624: Maximum Distance in Arrays Solution in Python – A Step-by-Step Guide

What Is LeetCode 624: Maximum Distance in Arrays?

In LeetCode 624: Maximum Distance in Arrays, you’re given a list of sorted integer arrays (e.g., [[1,2,3], [4,5], [1,2,3]]), and your task is to find the maximum absolute difference between any two elements, where each element comes from a different array. For example, in [[1,2,3], [4,5]], the max distance could be |5 - 1| = 4. The arrays are sorted in ascending order, and you must pick exactly one element from each of two different arrays. This problem tests your ability to optimize distance calculations across multiple datasets.

Problem Statement

• Input:
• arrays: A list of sorted integer arrays.
• Output: An integer—the maximum absolute difference between elements from different arrays.
• Rules:
• Each element must come from a distinct array.
• Arrays are sorted ascending.
• Compute |a - b| for all valid pairs, find max.

Constraints

• 2 ≤ arrays.length ≤ 100.
• 1 ≤ arrays[i].length ≤ 100.
• -10⁴ ≤ arrays[i][j] ≤ 10⁴.
• Each array is sorted in ascending order.

Examples

• Input: arrays = [[1,2,3], [4,5], [1,2,3]]
• Output: 4 (e.g., |5 - 1| between [4,5] and either [1,2,3])
• Input: arrays = [[1,4], [0,5]]
• Output: 5 (e.g., |5 - 0|)
• Input: arrays = [[1], [2]]
• Output: 1 (|2 - 1|)

These examples show the distance goal—let’s solve it!

Understanding the Problem: Maximizing Array Distances

To solve LeetCode 624: Maximum Distance in Arrays in Python, we need to find the maximum absolute difference between any two numbers from different arrays in a list. A naive approach might compare every pair, but since arrays are sorted, we can optimize by focusing on min and max values. We’ll use:

• Best Solution (Greedy with Min/Max Tracking): O(n) time, O(1) space—n is total arrays—fast and efficient.
• Alternative Solution (Brute-Force Pairwise): O(m * n²) time, O(1) space—m is avg array length—simple but slow.

Let’s start with the greedy solution, breaking it down for beginners.

Best Solution: Greedy with Min/Max Tracking

Why This Is the Best Solution

The greedy approach with min/max tracking is the top choice for LeetCode 624 because it’s efficient—O(n) time with O(1) space—and leverages the sorted nature of the arrays to avoid checking every element pair. By tracking the minimum and maximum values seen so far across arrays, it computes the max distance in one pass, fitting constraints (≤ 100 arrays). It’s like scanning regions and keeping the widest gap in mind!

How It Works

Think of this as measuring gaps across maps:

• Step 1: Initialize Min/Max:
• Start with first array’s min (first element) and max (last element).
• Step 2: Iterate Arrays:
• For each new array:
• Compute max distance using current array’s min/max with previous min/max.
• Update global max distance.
• Update min/max with current array’s values.
• Step 3: Return Result:
• Output the maximum distance found.

It’s like a distance tracker—greedy and smart!

Step-by-Step Example

Example: arrays = [[1,2,3], [4,5], [1,2,3]]

• Step 1: Init:
• curr_min = 1, curr_max = 3 (from [1,2,3]).
• max_dist = 0.
• Step 2: Process [4,5]:
• New min = 4, new max = 5.
• Distances: |4 - 3| = 1, |5 - 1| = 4.
• max_dist = 4.
• Update: curr_min = 1, curr_max = 5.
• Step 3: Process [1,2,3]:
• New min = 1, new max = 3.
• Distances: |1 - 5| = 4, |3 - 1| = 2.
• max_dist = 4 (no change).
• Update: curr_min = 1, curr_max = 5.
• Output: 4.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeclass Solution:
    def maxDistance(self, arrays: List[List[int]]) -> int:
        # Step 1: Initialize with first array
        curr_min = arrays[0][0]  # First element
        curr_max = arrays[0][-1]  # Last element
        max_dist = 0

        # Step 2: Iterate through remaining arrays
        for i in range(1, len(arrays)):
            new_min = arrays[i][0]
            new_max = arrays[i][-1]

            # Compute max distance with current array
            max_dist = max(max_dist, 
                          abs(new_max - curr_min),  # New max - prev min
                          abs(curr_max - new_min))  # Prev max - new min

            # Update min/max seen so far
            curr_min = min(curr_min, new_min)
            curr_max = max(curr_max, new_max)

        # Step 3: Return result
        return max_dist

• Lines 4-6: Init:
• Use first array’s min (0th) and max (-1th).
• Lines 9-17: Iterate:
• For each array, compute distances with prior min/max.
• Update max_dist and running min/max.
• Time Complexity: O(n)—one pass through arrays.
• Space Complexity: O(1)—few variables.

This is like a distance optimizer—fast and sleek!

Alternative Solution: Brute-Force Pairwise Comparison

Why an Alternative Approach?

The brute-force pairwise approach compares every element pair across different arrays—O(m * n²) time, O(1) space (m = avg array length, n = arrays). It’s simpler, requiring no optimization insight, but slow for large inputs (m, n ≤ 100). It’s like measuring every possible gap manually!

How It Works

Picture this as a full distance check:

• Step 1: Nested loops over arrays.
• Step 2: Compare all elements between pairs.
• Step 3: Track max distance.
• Step 4: Return result.

It’s like a thorough distance survey—check everything!

Step-by-Step Example

Example: arrays = [[1,2,3], [4,5]]

• Step 1: Pairs: ([1,2,3], [4,5]).
• Step 2: Compare:
• 1-4: |1-4| = 3.
• 1-5: |1-5| = 4.
• 2-4: |2-4| = 2.
• 2-5: |2-5| = 3.
• 3-4: |3-4| = 1.
• 3-5: |3-5| = 2.
• Step 3: Max = 4.
• Output: 4.

Code for Brute-Force Approach

Copy codeclass Solution:
    def maxDistance(self, arrays: List[List[int]]) -> int:
        # Step 1: Initialize max distance
        max_dist = 0

        # Step 2: Compare all pairs of arrays
        for i in range(len(arrays)):
            for j in range(i + 1, len(arrays)):
                # Compare all elements between arrays[i] and arrays[j]
                for num1 in arrays[i]:
                    for num2 in arrays[j]:
                        dist = abs(num1 - num2)
                        max_dist = max(max_dist, dist)

        # Step 3: Return result
        return max_dist

• Lines 6-11: Nested loops:
• Compare every element pair across different arrays.
• Time Complexity: O(m * n²)—n arrays, m elements per array.
• Space Complexity: O(1)—just a variable.

It’s a full distance scan—simple but slow!

Comparing the Two Solutions

• Greedy (Best):
• Pros: O(n) time, O(1) space, fast and elegant.
• Cons: Requires sorted array insight.
• Brute-Force (Alternative):
• Pros: O(m * n²) time, O(1) space, straightforward.
• Cons: Much slower.

Greedy wins for efficiency.

Additional Examples and Edge Cases

• Input: [[1], [2], [3]]
• Output: 2 (|3 - 1|).
• Input: [[1,1], [1,1]]
• Output: 0 (all pairs same).

Both handle these well.

Complexity Breakdown

• Greedy: Time O(n), Space O(1).
• Brute-Force: Time O(m * n²), Space O(1).

Greedy is optimal.

Key Takeaways

• Greedy: Min/max tracking—smart!
• Brute-Force: Full comparison—clear!
• Arrays: Distances are fun.
• Python Tip: Loops rock—see Python Basics.

Final Thoughts: Measure That Distance

LeetCode 624: Maximum Distance in Arrays in Python is a neat optimization challenge. The greedy approach offers speed and elegance, while brute-force provides a clear baseline. Want more? Try LeetCode 414: Third Maximum Number or LeetCode 628: Maximum Product of Three Numbers. Ready to map? Head to Solve LeetCode 624 on LeetCode and find that max distance today!