# Maximum Distance Between a Pair of Values
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-distance-between-a-pair-of-values)
Canonical: https://scaleengineer.com/dsa/problems/maximum-distance-between-a-pair-of-values
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## Problem
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 <= 105`
* `1 <= nums1[i], nums2[j] <= 105`
* Both `nums1` and `nums2` are **non-increasing**.

# Approaches
## Brute Force
This approach involves checking every possible valid pair of indices `(i, j)` and calculating their distance. We iterate through all `i` from `nums1` and for each `i`, we iterate through all `j` from `nums2` such that `j >= i`. If the pair is valid, we update the maximum distance found.
**Time:** O(N * M), where N is the length of `nums1` and M is the length of `nums2`. For each element in `nums1`, we potentially iterate through a large portion of `nums2`. · **Space:** O(1), as we only use a constant amount of extra space for variables.
**Pros:** Simple to understand and implement.
**Cons:** Highly inefficient due to the nested loops.; Will result in a 'Time Limit Exceeded' error for large input sizes as specified in the constraints.
### Explanation
The brute-force method is the most straightforward way to solve the problem. We can simply translate the problem statement into code. We need to find the maximum `j - i` among all pairs `(i, j)` that satisfy two conditions: `i <= j` and `nums1[i] <= nums2[j]`. We can use two nested loops to generate all possible pairs `(i, j)` where `i <= j`. The outer loop iterates `i` from `0` to `nums1.length - 1`, and the inner loop iterates `j` from `i` to `nums2.length - 1`. Inside the inner loop, we check the second condition, `nums1[i] <= nums2[j]`. If it holds, we have a valid pair, and we update our `maxDistance` with the current distance `j - i` if it's larger.

```java
class Solution {
    public int maxDistance(int[] nums1, int[] nums2) {
        int maxDistance = 0;
        int n = nums1.length;
        int m = nums2.length;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < m; j++) {
                if (nums1[i] <= nums2[j]) {
                    maxDistance = Math.max(maxDistance, j - i);
                }
            }
        }
        return maxDistance;
    }
}
```
### Algorithm
- Initialize a variable `maxDistance` to 0.
- Use a nested loop. The outer loop iterates through `nums1` with index `i` from 0 to `nums1.length - 1`.
- The inner loop iterates through `nums2` with index `j` from `i` to `nums2.length - 1`. This ensures the `i <= j` condition.
- Inside the inner loop, check if `nums1[i] <= nums2[j]`.
- If the condition is true, it's a valid pair. Calculate the distance `j - i` and update `maxDistance = max(maxDistance, j - i)`.
- After the loops complete, `maxDistance` will hold the result.

## Iteration with Binary Search
This approach improves upon the brute-force method by optimizing the search for the index `j`. For each index `i` in `nums1`, instead of linearly scanning `nums2`, we use binary search to find the largest valid index `j`. This is possible because `nums2` is a non-increasing (sorted) array.
**Time:** O(N * log M), where N is the length of `nums1` and M is the length of `nums2`. The outer loop runs N times, and each binary search takes O(log M) time. · **Space:** O(1), as we only use a few variables for the loops and binary search.
**Pros:** Significantly faster than the brute-force approach.; Passes the time limits for the given constraints.
**Cons:** More complex to implement correctly than the brute-force approach.; Not as efficient as the optimal two-pointer solution.
### Explanation
We can optimize the inner loop of the brute-force approach. For a fixed `i`, we want to find the largest `j` such that `j >= i` and `nums2[j] >= nums1[i]`. Since `nums2` is non-increasing, the values `nums2[j]` that are greater than or equal to `nums1[i]` will appear at the beginning of the array. We can use binary search to efficiently find the rightmost index `j` that satisfies this condition.

For each `i` from `0` to `nums1.length - 1`, we perform a binary search on the subarray `nums2` starting from index `i`. The search aims to find the largest `j` where `nums2[j] >= nums1[i]`. If such a `j` is found, we calculate `j - i` and update our `maxDistance`.

```java
class Solution {
    public int maxDistance(int[] nums1, int[] nums2) {
        int maxDistance = 0;
        int n = nums1.length;
        int m = nums2.length;
        for (int i = 0; i < n; i++) {
            // Binary search for the largest j >= i with nums2[j] >= nums1[i]
            int low = i;
            int high = m - 1;
            int best_j = -1;
            
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (nums2[mid] >= nums1[i]) {
                    // This is a potential answer, try to find a larger j
                    best_j = mid;
                    low = mid + 1;
                } else {
                    // nums2[mid] is too small, need to search in the left part
                    high = mid - 1;
                }
            }
            
            if (best_j != -1) {
                maxDistance = Math.max(maxDistance, best_j - i);
            }
        }
        return maxDistance;
    }
}
```
### Algorithm
- Initialize `maxDistance = 0`.
- Iterate `i` from 0 to `nums1.length - 1`.
- For each `i`, perform a binary search on `nums2` in the range `[i, nums2.length - 1]` for the value `nums1[i]`.
- The goal of the binary search is to find the largest index `j` such that `nums2[j] >= nums1[i]`.
- Let this index be `found_j`.
- If a valid `found_j` exists (i.e., it's not -1), update `maxDistance = max(maxDistance, found_j - i)`.
- Return `maxDistance`.

## Two Pointers
This is the most efficient approach, leveraging the non-increasing property of both arrays. We use two pointers, `i` for `nums1` and `j` for `nums2`, to traverse the arrays in a single combined pass, achieving linear time complexity.
**Time:** O(N + M), where N is the length of `nums1` and M is the length of `nums2`. Each pointer traverses its respective array at most once. · **Space:** O(1), as it only requires a few variables to store pointers and the result.
**Pros:** Optimal time complexity.; Very efficient as it processes both arrays in a single pass.; Simple implementation once the logic is understood.
**Cons:** The logic can be less intuitive to derive compared to the other approaches.
### Explanation
The key insight for the two-pointer approach is that as we iterate through `j` in `nums2`, the corresponding best `i` in `nums1` will also only move forward. Let's iterate through `nums2` with a pointer `j`. For each `j`, we want to find the smallest `i` such that `i <= j` and `nums1[i] <= nums2[j]`. A smaller `i` maximizes the distance `j - i`.

We can maintain a second pointer `i` for `nums1`. For a given `j`, if `nums1[i]` is too large (i.e., `nums1[i] > nums2[j]`), then we must increment `i` to find a smaller value in `nums1`. Since `nums1` is non-increasing, any index less than the current `i` would also have a value greater than `nums2[j]`, so we don't need to consider them. This means the pointer `i` never needs to be reset.

Both pointers `i` and `j` only move from left to right, ensuring that each element in both arrays is visited at most once.

```java
class Solution {
    public int maxDistance(int[] nums1, int[] nums2) {
        int i = 0;
        int maxDistance = 0;
        int n = nums1.length;
        int m = nums2.length;
        
        for (int j = 0; j < m; j++) {
            // For the current j, find the smallest i such that nums1[i] <= nums2[j].
            // The pointer i only moves forward.
            while (i < n && nums1[i] > nums2[j]) {
                i++;
            }
            
            // If we found such an i and it's a valid pair (i <= j)
            if (i < n && i <= j) {
                maxDistance = Math.max(maxDistance, j - i);
            }
        }
        return maxDistance;
    }
}
```
### Algorithm
- Initialize `i = 0` (pointer for `nums1`) and `maxDistance = 0`.
- Iterate `j` from 0 to `nums2.length - 1` (pointer for `nums2`).
- Inside the loop, advance pointer `i` as long as `i < nums1.length` and `nums1[i] > nums2[j]`. This finds the first `i` that could potentially form a valid pair with `j`.
- After the inner `while` loop, if `i < nums1.length` and `i <= j`, we have a valid pair `(i, j)`.
- Update `maxDistance = max(maxDistance, j - i)`.
- Since `i` is the smallest possible index for the current `j`, `j-i` is the maximum possible distance for this `j`.
- Return `maxDistance` after the loop finishes.

# Solutions
### JavaScript

```javascript
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number} */ var maxDistance =
  function (nums1, nums2) {
    let ans = 0;
    let m = nums1.length;
    let n = nums2.length;
    for (let i = 0; i < m; ++i) {
      let left = i;
      let right = n - 1;
      while (left < right) {
        const mid = (left + right + 1) >> 1;
        if (nums2[mid] >= nums1[i]) {
          left = mid;
        } else {
          right = mid - 1;
        }
      }
      ans = Math.max(ans, left - i);
    }
    return ans;
  };

```

### Java

```java
class Solution {
public
  int maxDistance(int[] nums1, int[] nums2) {
    int ans = 0;
    int m = nums1.length, n = nums2.length;
    for (int i = 0; i < m; ++i) {
      int left = i, right = n - 1;
      while (left < right) {
        int mid = (left + right + 1) >> 1;
        if (nums2[mid] >= nums1[i]) {
          left = mid;
        } else {
          right = mid - 1;
        }
      }
      ans = Math.max(ans, left - i);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxDistance(vector<int> &nums1, vector<int> &nums2) {
    int ans = 0;
    reverse(nums2.begin(), nums2.end());
    for (int i = 0; i < nums1.size(); ++i) {
      int j =
          nums2.size() -
          (lower_bound(nums2.begin(), nums2.end(), nums1[i]) - nums2.begin()) -
          1;
      ans = max(ans, j - i);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int: ans = 0 nums2 = nums2[:: - 1] for i, v in enumerate(nums1): j = len(nums2) - bisect_left(nums2, v) - 1 ans = max(ans, j - i) return ans

```