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.
Example 1:
Input: arrays = [[1,2,3],[4,5],[1,2,3]] Output: 4 Explanation: 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:
Input: arrays = [[1],[1]] Output: 0
Constraints:
m == arrays.length2 <= m <= 1051 <= arrays[i].length <= 500-104 <= arrays[i][j] <= 104arrays[i]is sorted in ascending order.- There will be at most
105integers in all the arrays.
Approach 01:
-
C++
-
Python
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>
class Solution {
public:
int maxDistance(std::vector<std::vector<int>>& arrays) {
int maxDistance = 0; // Initialize the maximum distance to zero
int currentMin = arrays[0][0]; // Start with the first array's minimum value
int currentMax = arrays[0].back(); // Start with the first array's maximum value
// Iterate through each array starting from the second one
for (int i = 1; i < arrays.size(); ++i) {
// Get the current array's first and last elements
int currentArrayFirst = arrays[i][0];
int currentArrayLast = arrays[i].back();
// Calculate distances using the first and last elements of the current array
int distanceFromMax = std::abs(currentArrayFirst - currentMax); // Distance from the current array's first element to current maximum
int distanceFromMin = std::abs(currentArrayLast - currentMin); // Distance from the current array's last element to current minimum
// Update the maximum distance if the current distances are greater
maxDistance = std::max(maxDistance, std::max(distanceFromMax, distanceFromMin));
// Update currentMin and currentMax to include the current array
currentMin = std::min(currentMin, currentArrayFirst); // Update current minimum value
currentMax = std::max(currentMax, currentArrayLast); // Update current maximum value
}
return maxDistance; // Return the largest distance found
}
};
from typing import List
class Solution:
def maxDistance(self, arrays: List[List[int]]) -> int:
maxDistance = 0 # Initialize the maximum distance to zero
currentMin, currentMax = arrays[0][0], arrays[0][-1] # Start with the first array's min and max values
# Iterate through each array starting from the second one
for array in arrays[1:]:
# Calculate distances using the first and last elements of the current array
distanceFromMax = abs(array[0] - currentMax) # Distance from the current array's first element to current maximum
distanceFromMin = abs(array[-1] - currentMin) # Distance from the current array's last element to current minimum
# Update the maximum distance if the current distances are greater
maxDistance = max(maxDistance, distanceFromMax, distanceFromMin)
# Update currentMin and currentMax to include the current array
currentMin = min(currentMin, array[0]) # Update current minimum value
currentMax = max(currentMax, array[-1]) # Update current maximum value
return maxDistance # Return the largest distance found
Time Complexity
- Iteration over Arrays:
The function iterates through each array in the input list, which takes \( O(n) \) time, where \( n \) is the number of arrays.
- Calculating Distances:
For each array, the function performs constant-time operations to calculate distances and update minimum and maximum values. These operations take \( O(1) \) time.
- Overall Time Complexity:
The overall time complexity is \( O(n) \), where \( n \) is the number of arrays.
Space Complexity
- Auxiliary Variables:
The function uses a constant amount of extra space for variables such as
maxDistance,currentMin, andcurrentMax. - Overall Space Complexity:
The overall space complexity is \( O(1) \) because the space used does not depend on the input size.