624. Maximum Distance in Arrays


Problem Description

In this problem, we are provided m separate arrays, each being sorted in ascending order. Our task is to find the maximum distance between any two integers where each integer is taken from a different array. The distance is defined as the absolute difference between those two integers. That is, if we take one integer a from one array and another integer b from a different array, the distance is |a - b|. We need to compute and return the maximum such distance possible.

Intuition

To solve this problem efficiently, we leverage the fact that each of the m arrays is sorted in ascending order. Given this property, the smallest element of each array will be at the 0-th index and the largest element at the last index.

To find the maximum distance, we need to make the difference as large as possible. This means we should consider the potential largest distance by taking the smallest element from one array and the largest from another array. So to maximize the distance, we always consider the minimum element from one array and the maximum element from the other.

The approach is to iterate through the arrays while tracking the smallest and largest elements we have seen so far. For each new array, we consider the distance between the current array's smallest element and the maximum element seen so far, and vice versa - the distance between the current array's largest element and the smallest element seen so far. The answer is the largest of all these distances.

Here is the step-by-step reasoning:

  1. Initialize ans to 0, which will keep track of the maximum distance.
  2. Take the smallest (mi) and largest (mx) elements from the first array to initiate tracking.
  3. Iterate through the remaining arrays starting from the second one. For each array:
    • Calculate the absolute difference between the current array's smallest element and mx (the largest element seen so far).
    • Calculate the absolute difference between the current array's largest element and mi (the smallest element seen so far).
    • Update ans with the largest value between ans, the first calculated difference, and the second calculated difference.
    • Update mi with the smallest value between mi (the smallest value found so far) and the smallest element of the current array.
    • Update mx with the largest value between mx (the largest value found so far) and the largest element of the current array.
  4. After finishing the iteration, return ans as the maximum distance found.

By only comparing the extreme ends of each array, we ensure that we are always considering the likely pairs to give us the maximum distance while maintaining a linear time complexity.

Learn more about Greedy patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which algorithm should you use to find a node that is close to the root of the tree?

Solution Approach

The solution follows a greedy strategy by keeping track of the smallest and the largest element found so far across all arrays. Here is how the implementation reflects the approach:

  • An initial answer ans is set to 0, which will hold the maximum distance.
  • The smallest element mi and the largest element mx from the first array are used to initialize the tracking.
  • Then, for every subsequent array, the implementation performs the following steps:
    1. Calculates two distances: the distance between the smallest element of the current array and the largest element mx seen so far (a = abs(arr[0] - mx)), and the distance between the largest element of the current array and the smallest element mi seen so far (b = abs(arr[-1] - mi)).
    2. The answer ans is updated to be the maximum of ans, a, and b.
    3. The current array's smallest element is considered to update mi using mi = min(mi, arr[0]) if it is smaller than the current mi.
    4. Similarly, the current array's largest element is used to update mx using mx = max(mx, arr[-1]) if it is larger than the current mx.

By using min() and max() functions, the elements mi and mx are continuously updated to always represent the smallest and largest element found up to the current point in iteration.

This approach guarantees each array is only visited once, making the overall time complexity O(m), where m is the number of arrays. There is no use of additional data structures, keeping space complexity to O(1) as it only uses a few variables for tracking the minimum, maximum, and the current answer.

The code directly follows this strategy and does not use any complex data structures or algorithms beyond basic conditional statements and math operations.

Here's a snippet of the main logic using the algorithm described:

1class Solution:
2    def maxDistance(self, arrays: List[List[int]]) -> int:
3        ans = 0
4        mi, mx = arrays[0][0], arrays[0][-1]
5        for arr in arrays[1:]:
6            a, b = abs(arr[0] - mx), abs(arr[-1] - mi)
7            ans = max(ans, a, b)
8            mi = min(mi, arr[0])
9            mx = max(mx, arr[-1])
10        return ans
Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

In a binary min heap, the minimum element can be found in:

Example Walkthrough

Let's say we have the following 3 sorted arrays:

  • Array 1: [1, 2, 3]
  • Array 2: [4, 5]
  • Array 3: [1, 5, 9]

Our goal is to find the maximum distance between any two integers from two different arrays.

  1. Initialize ans to 0, which will be used to keep track of the maximum distance found so far.
  2. We start with the first array and take its smallest and largest elements as the initial values for mi and mx respectively. In this case, mi is 1 and mx is 3.

Now, we iterate through the remaining arrays to calculate potential distances and update mi and mx.

  1. Moving to the second array [4, 5], we calculate the distance between the smallest element in this array 4 and the current mx 3 which is abs(4 - 3) = 1. We also calculate the distance between the largest element in this array 5 and the current mi 1 which is abs(5 - 1) = 4. We update ans to the maximum of ans, which is 0, and these new distances. ans is now 4. We also update mi and mx if necessary. Since 4 is greater than mi and 5 is greater than mx, we only update mx to 5.

  2. Next, we go to the third array [1, 5, 9]. We calculate the distance between 1 (the smallest element of this array) and the current largest mx, which is 5. The distance is abs(1 - 5) = 4. Then, we calculate the distance between 9 (the largest element of this array) and the current smallest mi, which is 1. The distance here is abs(9 - 1) = 8. We update ans to the maximum of ans and these new distances. ans is now updated to 8, which is the maximum distance found. We check if we need to update mi or mx. Since 1 is equal to current mi and 9 is greater than current mx, we update mx to 9.

Finally, after iterating through all arrays, we have the largest distance ans as 8, which is the correct maximum distance between two integers from two different arrays. Thus, we return 8.

Not Sure What to Study? Take the 2-min Quiz:

Is the following code DFS or BFS?

1void search(Node root) {
2  if (!root) return;
3  visit(root);
4  root.visited = true;
5  for (Node node in root.adjacent) {
6    if (!node.visited) {
7      search(node);
8    }
9  }
10}

Python Solution

1from typing import List
2
3class Solution:
4    def maxDistance(self, arrays: List[List[int]]) -> int:
5        # Initialize the maximum distance and the minimum and maximum values
6        max_distance = 0
7        min_value, max_value = arrays[0][0], arrays[0][-1]
8
9        # Iterate over the arrays starting from the second one
10        for array in arrays[1:]:
11            # Compute the potential distances between the current array's first or last element
12            # with the opposite ends of the known range (max_value and min_value)
13            distance_min_to_max = abs(array[0] - max_value)
14            distance_max_to_min = abs(array[-1] - min_value)
15          
16            # Update max_distance to be the maximum of the current max_distance and the new distances
17            max_distance = max(max_distance, distance_min_to_max, distance_max_to_min)
18          
19            # Update the overall min_value and max_value with the current array's values
20            min_value = min(min_value, array[0])
21            max_value = max(max_value, array[-1])
22      
23        # Return the computed maximum distance between any two pairs
24        return max_distance
25

Java Solution

1class Solution {
2
3    // Method to find the maximum distance between any pair of elements 
4    // from different arrays within the list of arrays.
5    public int maxDistance(List<List<Integer>> arrays) {
6        // Initializing 'ans' as 0 to hold the maximum distance encountered.
7        int maxDistance = 0;
8
9        // Assign the first element of the first array as the minimum known value 'min'.
10        int min = arrays.get(0).get(0);
11
12        // Assign the last element of the first array as the maximum known value 'max'.
13        int max = arrays.get(0).get(arrays.get(0).size() - 1);
14      
15        // Iterate over the remaining arrays in the list starting from the second array.
16        for (int i = 1; i < arrays.size(); ++i) {
17            List<Integer> array = arrays.get(i);
18
19            // Calculate the absolute difference between the first element of the current array 
20            // and the known maximum. This represents a potential max distance.
21            int distanceWithMax = Math.abs(array.get(0) - max);
22
23            // Calculate the absolute difference between the last element of the current array 
24            // and the known minimum. This represents a potential max distance.
25            int distanceWithMin = Math.abs(array.get(array.size() - 1) - min);
26
27            // Update 'maxDistance' with the greater of the two newly calculated distances 
28            // if either is larger than the current 'maxDistance'.
29            maxDistance = Math.max(maxDistance, Math.max(distanceWithMax, distanceWithMin));
30
31            // Update the known minimum value 'min' if the first item of the current array is smaller.
32            min = Math.min(min, array.get(0));
33
34            // Update the known maximum value 'max' if the last item of the current array is larger.
35            max = Math.max(max, array.get(array.size() - 1));
36        }
37
38        // Return the largest distance found.
39        return maxDistance;
40    }
41}
42

C++ Solution

1#include <vector>
2#include <algorithm> // include the algorithm header for using min, max functions
3
4class Solution {
5public:
6    int maxDistance(vector<vector<int>>& arrays) {
7        int maxDistance = 0; // maximum distance found so far
8        int minElement = arrays[0][0]; // initialize with the first element of the first array
9        int maxElement = arrays[0].back(); // initialize with the last element of the first array
10
11        // Start from the second array
12        for (int i = 1; i < arrays.size(); ++i) {
13            // Reference to the current array to avoid copying
14            auto& currentArray = arrays[i];
15          
16            // Calculate distance between the smallest element so far and the last element of the current array
17            int distanceToMin = abs(currentArray[0] - maxElement);
18          
19            // Calculate distance between the largest element so far and the first element of the current array
20            int distanceToMax = abs(currentArray.back() - minElement);
21          
22            // Update maxDistance with the largest of the three: itself, distanceToMin, distanceToMax
23            maxDistance = max({maxDistance, distanceToMin, distanceToMax});
24          
25            // Update minElement with the smaller between minElement and the first element of the current array
26            minElement = min(minElement, currentArray[0]);
27          
28            // Update maxElement with the larger between maxElement and the last element of the current array
29            maxElement = max(maxElement, currentArray.back());
30        }
31      
32        // Return the maximum distance found
33        return maxDistance;
34    }
35};
36

Typescript Solution

1// Importing the first and last functions from lodash for array manipulation
2import { first, last } from 'lodash';
3
4// Function to calculate the maximum distance between any pair of elements from different arrays
5function maxDistance(arrays: number[][]): number {
6    // Maximum distance found so far
7    let maxDistance = 0;
8    // Initialize with the first element of the first sub-array
9    let minElement = first(arrays[0]) as number;
10    // Initialize with the last element of the first sub-array
11    let maxElement = last(arrays[0]) as number;
12
13    // Start from the second sub-array
14    for (let i = 1; i < arrays.length; ++i) {
15        // Reference to the current sub-array to avoid copying
16        const currentArray = arrays[i];
17      
18        // Calculate distance between the smallest element so far and the last element of the current sub-array
19        const distanceToMin = Math.abs(first(currentArray) as number - maxElement);
20      
21        // Calculate distance between the largest element so far and the first element of the current sub-array
22        const distanceToMax = Math.abs(last(currentArray) as number - minElement);
23      
24        // Update maxDistance with the largest of the three: itself, distanceToMin, distanceToMax
25        maxDistance = Math.max(maxDistance, distanceToMin, distanceToMax);
26      
27        // Update minElement with the smaller between minElement and the first element of the current sub-array
28        minElement = Math.min(minElement, first(currentArray) as number);
29      
30        // Update maxElement with the larger between maxElement and the last element of the current sub-array
31        maxElement = Math.max(maxElement, last(currentArray) as number);
32    }
33  
34    // Return the maximum distance found
35    return maxDistance;
36}
37
Fast Track Your Learning with Our Quick Skills Quiz:

Which technique can we use to find the middle of a linked list?

Time and Space Complexity

Time Complexity

The time complexity of the given code is primarily determined by the loop that iterates over all elements of the arrays list, except the first element. In the worst case, where there are n arrays inside the arrays list, we iterate n - 1 times. Inside the loop, we execute a constant number of operations for each array: calculating the absolute difference between the first and last elements with mi and mx, updating ans, and updating mi and mx with the current array's first and last elements, respectively. Since all these operations inside the loop have a constant time complexity, the overall time complexity of the loop is O(n).

Hence, the total time complexity of the code is O(n).

Space Complexity

The space complexity is determined by the additional memory used by the program which is not part of the input. In the given code, we use a fixed number of variables (ans, mi, mx, a, b) that do not depend on the size of the input. No other dynamic data structures or recursive calls which could use additional space are involved. Therefore, the space complexity is O(1), which represents constant space usage.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫