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
- 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.
- The answer involves two different arrays, so the optimal pair must use the minimum of one array and the maximum of another.
- Sweep the arrays while maintaining the minimum of all arrays seen so far and the maximum of all arrays seen so far.
- For each new array, the best distance is
max(|array_max - seen_min|, |seen_max - array_min|). Update the running min/max afterwards. - 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_maxbefore 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.