Jobs

Interviews

Discussions

Maximum Distance in Arrays

Medium

Yahoo

4 views

Topics:

ArraysGreedy Algorithms

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.length
2 <= m <= 10⁵
1 <= arrays[i].length <= 500
-10⁴ <= arrays[i][j] <= 10⁴
arrays[i] is sorted in ascending order.
There will be at most 10⁵ integers in all the arrays.

Maximum Distance in Arrays

Medium

Yahoo

4 views

Topics:

ArraysGreedy Algorithms

You are given m arrays, where each array is sorted in ascending order.

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.length
2 <= m <= 10⁵
1 <= arrays[i].length <= 500
-10⁴ <= arrays[i][j] <= 10⁴
arrays[i] is sorted in ascending order.
There will be at most 10⁵ integers in all the arrays.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for integers within the sub-arrays, and can they be negative?
Can any of the input arrays be empty or null? What should I return in those cases?
If the overall input 'arrays' is empty or contains only one array, what should the output be?
Are the sub-arrays guaranteed to be sorted, or do I need to handle unsorted sub-arrays?
If multiple pairs achieve the maximum distance, is it acceptable to return any one of those pairs, or is there a specific requirement for choosing between them?

Brute Force Solution

Approach

The brute force approach to finding the maximum distance between elements in multiple lists involves checking every single possible pair of elements across all lists. We calculate the distance for each pair and, ultimately, select the largest distance we've found.

Here's how the algorithm would work step-by-step:

Take the first number from the first list.
Compare this number to every number in every other list.
Calculate the distance between the first number and each of the other numbers. The distance is the absolute difference between the two numbers.
Remember the largest distance found so far.
Now, take the second number from the first list, and repeat the process of comparing it to every number in every other list and calculating the distances.
Continue this process for every number in the first list.
Next, move to the second list, and repeat the whole process, comparing each of its numbers to every number in all the other lists.
Keep doing this for every single list until you've compared every possible pair of numbers.
At the end, the largest distance you remembered is the answer.

Code Implementation

def maximum_distance_in_arrays_brute_force(number_lists):
    maximum_distance = 0

    # Iterate through each list
    for first_list_index in range(len(number_lists)):
        first_list = number_lists[first_list_index]
        for first_number_index in range(len(first_list)):
            first_number = first_list[first_number_index]

            # Compare current number with every number in every other list
            for second_list_index in range(len(number_lists)):
                if first_list_index == second_list_index:
                    continue

                second_list = number_lists[second_list_index]
                for second_number_index in range(len(second_list)):
                    second_number = second_list[second_number_index]

                    current_distance = abs(first_number - second_number)
                    maximum_distance = max(maximum_distance, current_distance)

    #Brute force complete
    return maximum_distance

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n*m) – Let n be the total number of elements across all lists, and let m be the number of lists. The described algorithm iterates through each element in each list. For each element, it then iterates through all elements in all other lists to compute the distance. Therefore, for each element in the input, the algorithm performs operations proportional to the number of other elements. This results in approximately n * (n - size of the list that the current element belongs to) operations. In the worst case where all numbers are in one large array, this approximates n*n which is O(n^2). But if the numbers are distributed across m arrays such that the average size of each array is n/m, then it's closer to n * (n - n/m), but if we say on average we check a constant number in each of the other lists, then we have m nested loops so in the worst case is O(n*m).

Space Complexity

O(1) – The brute force approach only uses a single variable to track the maximum distance found so far. It iterates through the input arrays, comparing values and updating this single variable as needed. The amount of auxiliary space used does not depend on the size of the input arrays, denoted as N (where N represents the total number of elements across all lists). Therefore, the space complexity is constant.

Optimal Solution

Approach

The most efficient way to find the maximum distance between elements in multiple lists involves finding the smallest and largest values across all lists. We can then directly calculate the maximum potential distance using these extreme values, avoiding unnecessary comparisons.

Here's how the algorithm would work step-by-step:

Find the overall smallest number among all the lists.
Find the overall biggest number among all the lists.
For each list, calculate the distance between the biggest number overall and the smallest number in that specific list.
For each list, also calculate the distance between the smallest number overall and the biggest number in that specific list.
Keep track of the biggest distance you've found so far as you go through all the lists.
The biggest distance you kept track of is the answer.

Code Implementation

def max_distance(arrays):
    overall_smallest = arrays[0][0]
    overall_biggest = arrays[0][0]

    for array in arrays:
        overall_smallest = min(overall_smallest, min(array))
        overall_biggest = max(overall_biggest, max(array))

    maximum_distance = 0

    # Iterate to find the max distance from each array
    for array in arrays:

        smallest_in_current_array = min(array)
        biggest_in_current_array = max(array)

        # Calculate distance with overall biggest.
        distance1 = overall_biggest - smallest_in_current_array
        maximum_distance = max(maximum_distance, distance1)

        # Calculate distance with overall smallest.
        distance2 = biggest_in_current_array - overall_smallest
        maximum_distance = max(maximum_distance, distance2)

    return maximum_distance

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(N) – Finding the overall smallest and largest numbers requires iterating through all elements of all arrays once. Iterating through each list to calculate the distances involves another single pass through all elements. Thus, the time complexity is dominated by these two linear traversals of the input data, where N is the total number of elements across all arrays, resulting in O(N) time complexity.

Space Complexity

O(1) – The algorithm uses a constant number of variables to store the overall smallest number, overall biggest number, the smallest number in the current list, the biggest number in the current list, and the maximum distance found so far. These variables consume a fixed amount of memory regardless of the input size N, where N represents the total number of elements across all lists. No additional data structures like lists or hash maps are created that scale with the input size. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty list of arrays	Return 0 immediately as no distance can be calculated with an empty input.
List of arrays contains an empty array	Ignore the empty array as it doesn't contribute to the maximum distance.
All arrays contain only one element	The maximum distance will be the difference between the largest and smallest of those single elements.
All arrays contain the same set of numbers	The maximum distance would be 0 if all arrays contain the exact same value; otherwise, the difference between the global max and min values should be returned.
Integer overflow when calculating the distance between max and min elements	Use long data type when calculating the distance to avoid overflow.
Very large input list causing performance issues	Iterate only once through the arrays, keeping track of the global maximum and minimum, ensuring O(n) time complexity.
Arrays are sorted in descending order.	The algorithm should correctly identify the maximum and minimum values regardless of the order of elements in each array.
Arrays with extreme boundary values (INT_MAX, INT_MIN)	Properly handle potential integer overflows or underflows when comparing these values.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for integers within the sub-arrays, and can they be negative?
Can any of the input arrays be empty or null? What should I return in those cases?
If the overall input 'arrays' is empty or contains only one array, what should the output be?
Are the sub-arrays guaranteed to be sorted, or do I need to handle unsorted sub-arrays?
If multiple pairs achieve the maximum distance, is it acceptable to return any one of those pairs, or is there a specific requirement for choosing between them?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first number from the first list.
Compare this number to every number in every other list.
Calculate the distance between the first number and each of the other numbers. The distance is the absolute difference between the two numbers.
Remember the largest distance found so far.
Now, take the second number from the first list, and repeat the process of comparing it to every number in every other list and calculating the distances.
Continue this process for every number in the first list.
Next, move to the second list, and repeat the whole process, comparing each of its numbers to every number in all the other lists.
Keep doing this for every single list until you've compared every possible pair of numbers.
At the end, the largest distance you remembered is the answer.

Code Implementation

def maximum_distance_in_arrays_brute_force(number_lists):
    maximum_distance = 0

    # Iterate through each list
    for first_list_index in range(len(number_lists)):
        first_list = number_lists[first_list_index]
        for first_number_index in range(len(first_list)):
            first_number = first_list[first_number_index]

            # Compare current number with every number in every other list
            for second_list_index in range(len(number_lists)):
                if first_list_index == second_list_index:
                    continue

                second_list = number_lists[second_list_index]
                for second_number_index in range(len(second_list)):
                    second_number = second_list[second_number_index]

                    current_distance = abs(first_number - second_number)
                    maximum_distance = max(maximum_distance, current_distance)

    #Brute force complete
    return maximum_distance

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Find the overall smallest number among all the lists.
Find the overall biggest number among all the lists.
For each list, calculate the distance between the biggest number overall and the smallest number in that specific list.
For each list, also calculate the distance between the smallest number overall and the biggest number in that specific list.
Keep track of the biggest distance you've found so far as you go through all the lists.
The biggest distance you kept track of is the answer.

Code Implementation

def max_distance(arrays):
    overall_smallest = arrays[0][0]
    overall_biggest = arrays[0][0]

    for array in arrays:
        overall_smallest = min(overall_smallest, min(array))
        overall_biggest = max(overall_biggest, max(array))

    maximum_distance = 0

    # Iterate to find the max distance from each array
    for array in arrays:

        smallest_in_current_array = min(array)
        biggest_in_current_array = max(array)

        # Calculate distance with overall biggest.
        distance1 = overall_biggest - smallest_in_current_array
        maximum_distance = max(maximum_distance, distance1)

        # Calculate distance with overall smallest.
        distance2 = biggest_in_current_array - overall_smallest
        maximum_distance = max(maximum_distance, distance2)

    return maximum_distance

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty list of arrays	Return 0 immediately as no distance can be calculated with an empty input.
List of arrays contains an empty array	Ignore the empty array as it doesn't contribute to the maximum distance.
All arrays contain only one element	The maximum distance will be the difference between the largest and smallest of those single elements.
All arrays contain the same set of numbers	The maximum distance would be 0 if all arrays contain the exact same value; otherwise, the difference between the global max and min values should be returned.
Integer overflow when calculating the distance between max and min elements	Use long data type when calculating the distance to avoid overflow.
Very large input list causing performance issues	Iterate only once through the arrays, keeping track of the global maximum and minimum, ensuring O(n) time complexity.
Arrays are sorted in descending order.	The algorithm should correctly identify the maximum and minimum values regardless of the order of elements in each array.
Arrays with extreme boundary values (INT_MAX, INT_MIN)	Properly handle potential integer overflows or underflows when comparing these values.