1855.maximum-distance-between-a-pair-of-values.md

1855. Maximum Distance Between a Pair of Values

Hints

• What if you fix an index in nums1 and try to find the rightmost valid index in nums2?
• Both arrays are non-increasing. Can you leverage this property for efficient search?
• Is there a way to avoid checking every possible pair?

Breakdowns

1. For each index i in nums1, how do you efficiently find the largest j in nums2 such that nums1[i] <= nums2[j] and i <= j?

Try binary search or two pointers in sorted array to avoid brute force.

2. Can you process both arrays in a single pass?

Try to use two pointers to move forward only when the condition is met.

Key Insights

For each i, you want the rightmost j (with i <= j) such that nums1[i] <= nums2[j].

The problem is a classic two pointers or binary search on sorted arrays pattern. Due to the sorted nature, this is perfect for:

• Binary search: To find the rightmost j for each i in logarithmic time.
• Two pointers: Since both arrays are non-increasing, for each i, the valid j (where nums1[i] <= nums2[j]) is monotonic: as i increases, the possible j does not decrease.

Binary Search

Give the first number nums1[i], there are three cases below, and we're looking for the last number nums2[j] that satisfies the condition: nums1[i] <= nums2[j].

                 nums1[i]

// in nums2
|------------|--------------|-------------|
  > nums1[i]   == nums1[i]  ^  < nums1[i]
                            |
                            * The last number that satisfies the condition

We can iterate through nums1 and use binary search to find the upper bound of nums1[i] in nums2, that is to find the last index j in nums2 such that nums2[j] >= nums1[i] and j >= i. This leverages the non-increasing order of both arrays.

fun maxDistance(nums1: IntArray, nums2: IntArray): Int {
    var maxDistance = 0
    for (i in nums1.indices) {
        val j = upperBound(nums2, nums1[i])
        if (j - i > 0) {
            maxDistance = maxOf(maxDistance, j - i)
        }
    }
    return maxDistance
}

/**
 * Search for the last element s.t. target <= nums[j] (nums1[i] <= nums2[j]).
 */
private fun upperBound(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1
    while (left <= right) {
        val middle = left + (right - left) / 2
        val feasible = target <= nums[middle]
        if (feasible) {
            left = middle + 1
        } else {
            right = middle - 1
        }
    }
    return right
}

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

Two Pointers

For each i:

1. As long as the condition nums1[i] <= nums2[j] is met, we can move j as far as possible. We update the answer with the maximum distance while j is moving. (The first implementation) Or we can move j to the rightmost position until the condition is not met, then update the answer. (The second implementation)
2. If the condition is not met, we move i to the next position.

fun maxDistance(nums1: IntArray, nums2: IntArray): Int {
    val n = nums2.size
    var j = 0
    var maxDistance = 0
    for (i in nums1.indices) {
        while (j < n && nums1[i] <= nums2[j]) {
            j++
        }
        maxDistance = maxOf(maxDistance, j - 1 - i)
    }
    return maxDistance
}

// Or equivalently
fun maxDistance(nums1: IntArray, nums2: IntArray): Int {
    val m = nums1.size
    val n = nums2.size
    var i = 0
    var j = 0
    var maxDistance = 0
    while (i < m && j < n) {
        val first = nums1[i]
        val second = nums2[j]
        if (first <= second) {
            maxDistance = maxOf(maxDistance, j - i)
            j++
        } else {
            i++
        }
    }
    return maxDistance
}

• Time Complexity: O(m + n)
• Space Complexity: O(1)

Edge Cases

• nums1 or nums2 has only one element.
• All elements in nums1 are greater than those in nums2 (should return 0).
• All elements in nums1 are less than or equal to those in nums2 (should return the largest possible distance).
• The valid pair is only at the start or end of the arrays.
• Arrays with duplicate values.

Pitfalls

• Forgetting to check j >= i (the problem requires i <= j).
• Not handling the case when no valid j exists for a given i (should not update the answer in this case).

Similar or Follow-up Problems

• 624. Maximum Distance in Arrays
• 1014. Best Sightseeing Pair