⚡Flashcard Drill➔
NeetCode #22LC-624MediumArrays & HashingNC Algo100
← Back to All Problems

#22 · #624 · Maximum Distance in Arrays(数组列表中的最大距离)

📌 Problem Statement & Constraints

You are given m arrays, each sorted in ascending order. Pick exactly one integer from two different arrays and maximise |a - b|. Return the maximum possible distance. Constraints: 2 <= m <= 10^5, 1 <= arrays[i].length <= 500, each array is sorted ascending.

💡 Core Algorithmic Approaches

  1. Because each array is sorted, its minimum is the first element and its maximum is the last. The best candidate from an array is therefore one of those two ends.
  2. The answer involves two different arrays, so the optimal pair must use the minimum of one array and the maximum of another.
  3. Sweep the arrays while maintaining the minimum of all arrays seen so far and the maximum of all arrays seen so far.
  4. For each new array, the best distance is max(|array_max - seen_min|, |seen_max - array_min|). Update the running min/max afterwards.
  5. Updating after the comparison is essential: it guarantees the two arrays are distinct.

💻 Benchmark Python3 Implementation

class Solution:
    def maxDistance(self, arrays: List[List[int]]) -> int:
        res = 0
        seen_min = arrays[0][0]            # min over arrays processed so far
        seen_max = arrays[0][-1]           # max over arrays processed so far
        for a in arrays[1:]:
            # compare BEFORE updating so the two ends come from different arrays
            res = max(res, abs(a[-1] - seen_min), abs(seen_max - a[0]))
            seen_min = min(seen_min, a[0])
            seen_max = max(seen_max, a[-1])
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m): one pass over the arrays, with O(1) work per array. There is no need to examine the interior elements because each array is sorted.
💾 Space Complexity
O(1): only the running minimum and maximum.

⚠️ Interview Pitfalls & Follow-ups

  • Updating seen_min / seen_max before computing the distance: an array would be allowed to pair with itself, which the problem forbids.
  • Scanning every element of every array: unnecessary given the sortedness; O(total elements) instead of O(m).
  • Taking the global minimum and global maximum: they may come from the same array, so you must exclude that case.
  • Assuming the arrays are not sorted: the constraints guarantee ascending order, which is what justifies using only the two ends.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems