Maximum Distance Between a Pair of Values

#923 Most AskedMedium

Maximum Distance Between a Pair of Values #923 Most Asked

Medium

Google

6 views

Topics:

ArraysTwo Pointers

You are given two non-increasing 0-indexed integer arrays nums1 and nums2.

A pair of indices (i, j), where 0 <= i < nums1.length and 0 <= j < nums2.length, is valid if both i <= j and nums1[i] <= nums2[j]. The distance of the pair is j - i.

Return the maximum distance of any valid pair (i, j). If there are no valid pairs, return 0.

An array arr is non-increasing if arr[i-1] >= arr[i] for every 1 <= i < arr.length.

Example 1:

Input: nums1 = [55,30,5,4,2], nums2 = [100,20,10,10,5]
Output: 2
Explanation: The valid pairs are (0,0), (2,2), (2,3), (2,4), (3,3), (3,4), and (4,4).
The maximum distance is 2 with pair (2,4).

Example 2:

Input: nums1 = [2,2,2], nums2 = [10,10,1]
Output: 1
Explanation: The valid pairs are (0,0), (0,1), and (1,1).
The maximum distance is 1 with pair (0,1).

Example 3:

Input: nums1 = [30,29,19,5], nums2 = [25,25,25,25,25]
Output: 2
Explanation: The valid pairs are (2,2), (2,3), (2,4), (3,3), and (3,4).
The maximum distance is 2 with pair (2,4).

Constraints:

1 <= nums1.length, nums2.length <= 10⁵
1 <= nums1[i], nums2[j] <= 10⁵
Both nums1 and nums2 are non-increasing.

Try coding it in LeetCode

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 are the possible ranges for the integer values within the two input arrays?
Can either of the input arrays be null or empty?
If there is no valid pair (i.e., no i < j where nums1[i] <= nums2[j]), what value should I return?
Is there a maximum size limit for the input arrays?
Are the arrays guaranteed to be sorted?

Brute Force Solution

Approach

The brute force method for finding the maximum distance between two suitable numbers in a list involves examining every possible pair of numbers to see if they meet the required conditions. We calculate the distance for each valid pair and keep track of the largest distance found. Eventually, after checking every combination, the largest distance is revealed.

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

Consider the first number in the list.
Compare that number to every number that appears after it in the list.
For each pair, check if the first number is bigger than or equal to the second number (this is the condition we must meet).
If the condition is met, calculate the distance between the positions of those two numbers in the list.
Keep track of the largest distance that you've calculated so far.
Move on to the next number in the list and repeat the process of comparing it to all the numbers that come after it.
Continue this process until you have considered every possible pair of numbers in the list.
The largest distance you've kept track of is the maximum distance between a pair of values that meets the condition.

Code Implementation

def max_distance_brute_force(numbers):
    max_distance = 0
    list_length = len(numbers)

    for left_index in range(list_length):

        # Iterate through the list, starting from the element after left_index
        for right_index in range(left_index + 1, list_length):

            # Ensure condition is met before calculating distance.
            if numbers[left_index] >= numbers[right_index]:

                # Calculate the distance between the indices.
                current_distance = right_index - left_index

                # Update max_distance if current distance is greater.
                if current_distance > max_distance:
                    max_distance = current_distance

    return max_distance

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input array of size n. For each element at index i, it compares it with all subsequent elements at indices j > i. In the worst-case scenario, for each of the n elements, the inner loop iterates a decreasing number of times, from n-1 down to 0. The total number of comparisons and distance calculations is proportional to n * (n-1) / 2. Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The provided brute force algorithm only maintains a few constant-size variables such as the current maximum distance found and loop indices. It does not create any auxiliary data structures that scale with the input size N (the length of the list). Therefore, the space required by the algorithm remains constant, irrespective of the input size. The auxiliary space complexity is O(1).

Optimal Solution

Approach

The optimal approach leverages the fact that we only care about the *maximum* distance. This allows us to avoid checking unnecessary pairs. The core idea is to maintain a running 'best' distance while strategically exploring potential pairs from the beginning of the first list to the end of the second list, and updating our best distance as we go.

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

Begin by considering the first value in the first list and comparing it with values in the second list from the beginning.
Keep moving through the second list as long as the values there are less than or equal to the value from the first list we are currently looking at. As you move, keep track of the maximum difference encountered so far.
Once you find a value in the second list which is greater than the value from the first list, stop iterating through the second list.
Move to the next value in the first list. Since we're looking for the *maximum* distance, only consider this value if it's less than or equal to the previous value from the first list. If it's larger, we can safely skip it because it won't yield a larger distance than what we've already found.
Repeat the process of moving through the second list (starting from the beginning or a previously saved position) to calculate potential distances.
Continue these steps until you've gone through all relevant values in the first list.
The largest difference you've kept track of is the maximum distance between a pair of values.

Code Implementation

def max_distance(list1, list2):
    maximum_difference = -1
    first_list_index = 0
    second_list_index = 0

    while first_list_index < len(list1) and second_list_index < len(list2):
        # Only proceed if the current element in first list is
        # not greater than element in the second list
        if list1[first_list_index] <= list2[second_list_index]:
            difference = list2[second_list_index] - list1[first_list_index]
            maximum_difference = max(maximum_difference, difference)
            second_list_index += 1
        else:
            # If current element in list1 is greater, reset index
            first_list_index += 1
            second_list_index = 0

    return maximum_difference

Big(O) Analysis

Time Complexity

O(n) – The outer loop iterates through `nums1` which has a length let's call `n`. The crucial point is that the inner loop iterates through `nums2` (also of length `n` in the worst-case where nums1 and nums2 have the same length) but the index within `nums2` either remains the same or advances during each iteration of the outer loop. The index of `nums2` is never reset to 0. Thus the inner loop cumulatively visits each element of `nums2` at most once. Therefore, the overall time complexity is driven by a single pass through both lists, so the time complexity is O(n+n) which simplifies to O(n).

Space Complexity

O(1) – The described algorithm iterates through the input lists and maintains a running maximum distance. It uses a few variables to keep track of indices and the current maximum difference, but the number of these variables remains constant regardless of the size of the input lists. Therefore, the auxiliary space used is constant and independent of the input size, which means the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty array input	Return 0 immediately, as no distance can be calculated.
Arrays of different sizes	The problem assumes same sized arrays, ensure input validation exists and define behavior (throw error, truncate).
Monotonically decreasing array 'nums1'	Iterate through 'nums2' in its entirety to find the maximal distance.
Monotonically increasing array 'nums2'	The first valid pair will yield the maximal distance, so the algorithm can potentially terminate early.
Integer overflow when calculating the distance (j - i)	Use appropriate data types (long) to store the indices or the distance if necessary to avoid overflow.
All elements in nums1 are greater than or equal to all elements in nums2.	Return 0 as no valid i and j can satisfy the condition nums1[i] <= nums2[j].
Large arrays to ensure time complexity	Verify the chosen algorithm has an optimal time complexity (O(n) ideally) to avoid timeouts.
Arrays containing extremely large or small numbers.	Ensure the comparison nums1[i] <= nums2[j] is performed correctly with the given data types, and no precision issues occur.

Empty array input

How to Handle:

Return 0 immediately, as no distance can be calculated.

Arrays of different sizes

How to Handle:

The problem assumes same sized arrays, ensure input validation exists and define behavior (throw error, truncate).

Monotonically decreasing array 'nums1'

How to Handle:

Iterate through 'nums2' in its entirety to find the maximal distance.

Monotonically increasing array 'nums2'

How to Handle:

The first valid pair will yield the maximal distance, so the algorithm can potentially terminate early.

Integer overflow when calculating the distance (j - i)

How to Handle:

Use appropriate data types (long) to store the indices or the distance if necessary to avoid overflow.

All elements in nums1 are greater than or equal to all elements in nums2.

How to Handle:

Return 0 as no valid i and j can satisfy the condition nums1[i] <= nums2[j].

Large arrays to ensure time complexity

How to Handle:

Verify the chosen algorithm has an optimal time complexity (O(n) ideally) to avoid timeouts.

Arrays containing extremely large or small numbers.

How to Handle:

Ensure the comparison nums1[i] <= nums2[j] is performed correctly with the given data types, and no precision issues occur.