We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Distance Between a Pair of Values

Number: 1984

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given two non-increasing integer arrays nums1 and nums2, a pair of indices (i, j) is valid if i <= j and nums1[i] <= nums2[j]. The distance for a valid pair is defined as j - i. The task is to determine the maximum distance among all valid pairs. If no valid pairs exist, return 0.

Key Insights

  • Both arrays are sorted in non-increasing order.
  • A two-pointer approach can be leveraged to traverse both arrays in linear time.
  • By maintaining pointers i and j (with j always >= i), we can efficiently check the condition and update the maximum distance.
  • When the condition nums1[i] <= nums2[j] holds, increasing j can potentially widen the distance.
  • When the condition fails, it's necessary to increment i to try to meet the condition.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of nums1 and m is the length of nums2. Space Complexity: O(1)

Solution

The solution uses a two-pointer technique that takes advantage of the sorted (non-increasing) order of both arrays. Initialize two pointers, i and j, starting at the beginning of nums1 and nums2 respectively. While both pointers are within the bounds of their arrays, check if the current pair (i, j) is valid (i.e. nums1[i] <= nums2[j]). If valid, update the maximum distance and increment j to try and get a larger distance. If it is not valid, increment i to try and meet the condition. Make sure that j is always at least equal to i. This approach ensures that each array is traversed at most once, leading to an efficient solution.

Code Solutions

# Python implementation for Maximum Distance Between a Pair of Values

def maxDistance(nums1, nums2):
    # Initialize pointers for nums1 and nums2
    i, j = 0, 0
    max_dist = 0  # Variable to store the maximum distance found
    n, m = len(nums1), len(nums2)
    
    # Loop until either pointer reaches the end of its array
    while i < n and j < m:
        # Check if current pair (i, j) is valid: i <= j and nums1[i] <= nums2[j]
        if nums1[i] <= nums2[j]:
            # If valid, calculate distance and update max_dist if this is larger
            max_dist = max(max_dist, j - i)
            j += 1  # Move pointer j to search for a potentially larger distance
        else:
            i += 1  # If not valid, move pointer i to try to satisfy the condition
            # Ensure that pointer j is always at least equal to pointer i
            if j < i:
                j = i
    return max_dist

# Example usage:
print(maxDistance([55, 30, 5, 4, 2], [100, 20, 10, 10, 5]))
← Back to All Questions