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 themaximum distance of any valid pair (i, j). If there are no valid pairs, return0.

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

Examples

Example 1

1
2
3
4

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

1
2
3
4

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

1
2
3
4

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^5
  • 1 <= nums1[i], nums2[j] <= 10^5
  • Both nums1 and nums2 are non-increasing.

Solution

Method 1 – Two Pointers

Intuition

Since both arrays are non-increasing, we can use two pointers to efficiently find the maximum distance for valid pairs. For each index in nums1, we move the pointer in nums2 as far as possible while maintaining the constraints.

Approach

  1. Initialize two pointers i (for nums1) and j (for nums2).
  2. For each i from 0 to len(nums1)-1:
    • Move j forward as long as j < len(nums2) and nums2[j] >= nums1[i].
    • If j > i, update the answer with j-1 - i.
  3. Return the maximum distance found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int ans = 0, j = 0, n1 = nums1.size(), n2 = nums2.size();
        for (int i = 0; i < n1; ++i) {
            while (j < n2 && nums2[j] >= nums1[i]) ++j;
            if (j-1 >= i) ans = max(ans, j-1-i);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func maxDistance(nums1 []int, nums2 []int) int {
    ans, j := 0, 0
    n1, n2 := len(nums1), len(nums2)
    for i := 0; i < n1; i++ {
        for j < n2 && nums2[j] >= nums1[i] {
            j++
        }
        if j-1 >= i && j-1-i > ans {
            ans = j-1-i
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int maxDistance(int[] nums1, int[] nums2) {
        int ans = 0, j = 0, n1 = nums1.length, n2 = nums2.length;
        for (int i = 0; i < n1; i++) {
            while (j < n2 && nums2[j] >= nums1[i]) j++;
            if (j-1 >= i) ans = Math.max(ans, j-1-i);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun maxDistance(nums1: IntArray, nums2: IntArray): Int {
        var ans = 0
        var j = 0
        for (i in nums1.indices) {
            while (j < nums2.size && nums2[j] >= nums1[i]) j++
            if (j-1 >= i) ans = maxOf(ans, j-1-i)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def maxDistance(self, nums1: list[int], nums2: list[int]) -> int:
        ans = 0
        j = 0
        n1, n2 = len(nums1), len(nums2)
        for i in range(n1):
            while j < n2 and nums2[j] >= nums1[i]:
                j += 1
            if j-1 >= i:
                ans = max(ans, j-1-i)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn max_distance(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
        let mut ans = 0;
        let mut j = 0;
        let n1 = nums1.len();
        let n2 = nums2.len();
        for i in 0..n1 {
            while j < n2 && nums2[j] >= nums1[i] {
                j += 1;
            }
            if j > 0 && j-1 >= i {
                ans = ans.max(j-1-i);
            }
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    maxDistance(nums1: number[], nums2: number[]): number {
        let ans = 0, j = 0, n1 = nums1.length, n2 = nums2.length;
        for (let i = 0; i < n1; i++) {
            while (j < n2 && nums2[j] >= nums1[i]) j++;
            if (j-1 >= i) ans = Math.max(ans, j-1-i);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n1 + n2), where n1 and n2 are the lengths of the arrays. Each pointer moves at most once through its array.
  • 🧺 Space complexity: O(1), as only a few variables are used.