236. Maximum Distance in Arrays
Medium
Running Extrema
Array
Problem
You are given multiple integer arrays, each sorted in non-decreasing order. Choose one integer from one array and another integer from a different array. Return the maximum possible absolute difference between the two chosen integers.
Examples
Example 1
Input: [[1,2,3],[4,5],[1,2,3]]
Output: 4
Example 2
Input: [[1],[1]]
Output: 0
Example 3
Input: [[-10,-5],[0,3],[8,12]]
Output: 22
Constraints
� 2 <= arrays.length <= 100000
� 1 <= arrays[i].length
� Each arrays[i] is sorted in non-decreasing order.
Hints
?? Only the first and last value of each sorted array can participate in the maximum distance.
?? Maintain the global minimum and maximum from arrays processed earlier.
?? Compare the current array only against extrema belonging to earlier arrays before updating them.
Expected Complexity
Time: O(k)
Space: O(1)
Follow-up
Can you solve it in one pass without flattening or sorting all values?
Practice Notes
Attempts: 0
Time spent: 0min
Hints used: 0
JavaScript
00:00
Loading...
Case 1
Case 2
Case 3
Input
[[1,2,3],[4,5],[1,2,3]]Expected
4