Code Implementation

class Solution:
    def maxDistance(self, nums1, nums2):
        max_dist = 0
        i = 0
        j = 0
        n1 = len(nums1)
        n2 = len(nums2)
        while i < n1 and j < n2:
            if nums1[i] <= nums2[j]:
                max_dist = max(max_dist, j - i)
                j += 1
            else:
                i += 1
        return max_dist
      

class Solution {
public:
    int maxDistance(vector<int>& nums1, vector<int>& nums2) {
        int max_dist = 0;
        int i = 0, j = 0;
        int n1 = nums1.size(), n2 = nums2.size();
        while (i < n1 && j < n2) {
            if (nums1[i] <= nums2[j]) {
                max_dist = max(max_dist, j - i);
                j++;
            } else {
                i++;
            }
        }
        return max_dist;
    }
};
      

class Solution {
    public int maxDistance(int[] nums1, int[] nums2) {
        int maxDist = 0;
        int i = 0, j = 0;
        int n1 = nums1.length, n2 = nums2.length;
        while (i < n1 && j < n2) {
            if (nums1[i] <= nums2[j]) {
                maxDist = Math.max(maxDist, j - i);
                j++;
            } else {
                i++;
            }
        }
        return maxDist;
    }
}
      

var maxDistance = function(nums1, nums2) {
    let maxDist = 0;
    let i = 0, j = 0;
    let n1 = nums1.length, n2 = nums2.length;
    while (i < n1 && j < n2) {
        if (nums1[i] <= nums2[j]) {
            maxDist = Math.max(maxDist, j - i);
            j++;
        } else {
            i++;
        }
    }
    return maxDist;
};
      

Problem Description

You are given two non-increasing (i.e., sorted in descending order) integer arrays nums1 and nums2. Your task is to find the maximum distance between a pair of indices (i, j) such that:

• 0 <= i < nums1.length
• 0 <= j < nums2.length
• i <= j
• nums1[i] <= nums2[j]

The distance is defined as j - i. Find the largest possible distance among all valid pairs (i, j). Each index can only be used once per pair. You must not reuse elements.

Thought Process

At first glance, you might consider checking every possible pair of indices (i, j) to see if they satisfy the constraints. This brute-force approach would involve two nested loops, resulting in a time complexity of O(N^2), which is inefficient for large arrays.

However, notice that both arrays are sorted in non-increasing order. This property allows us to use a much faster approach, similar to the two-pointer technique. Instead of checking every possible pair, we can efficiently "slide" pointers through the arrays to find the maximum distance. The key insight is that as you move forward in nums2 (increasing j), you can only move i forward when needed, which ensures you never revisit the same pair.

This optimization reduces the problem to a linear scan, making it much more efficient.

Solution Approach

Let's break down the optimized solution step-by-step:

1. Initialize two pointers: Start with i = 0 for nums1 and j = 0 for nums2. Also, initialize a variable max_dist to keep track of the largest distance found.
2. Iterate with two pointers:
   • While both i and j are within their respective array bounds:
   • Check if nums1[i] <= nums2[j]. If so, this is a valid pair and you can calculate j - i. Update max_dist if this distance is larger than the current maximum.
   • Then increment j to try to find an even larger distance for the same i.
   • If nums1[i] > nums2[j], increment i to try a smaller value from nums1 (since the arrays are non-increasing).
3. Repeat until done: Continue this process until either pointer reaches the end of its array.
4. Return the result: Once finished, max_dist contains the answer.

This method is efficient because each pointer only moves forward, ensuring an overall time complexity of O(N).

Example Walkthrough

Consider the following input:

• nums1 = [30, 29, 19, 5]
• nums2 = [25, 25, 21, 19, 15]

Let's trace the process:

1. Start: i = 0, j = 0. nums1[0] = 30, nums2[0] = 25. Since 30 > 25, increment i to 1.
2. i = 1, j = 0. nums1[1] = 29, nums2[0] = 25. 29 > 25, increment i to 2.
3. i = 2, j = 0. nums1[2] = 19, nums2[0] = 25. 19 <= 25, valid pair. Distance is 0 - 2 = -2 (invalid, since i <= j must also hold). But j = 0, so increment j to 1.
4. i = 2, j = 1. nums2[1] = 25. 19 <= 25, valid. Distance is 1 - 2 = -1. Still negative, increment j to 2.
5. i = 2, j = 2. nums2[2] = 21. 19 <= 21, valid. Distance is 2 - 2 = 0. Update max_dist to 0. Increment j to 3.
6. i = 2, j = 3. nums2[3] = 19. 19 <= 19, valid. Distance is 3 - 2 = 1. Update max_dist to 1. Increment j to 4.
7. i = 2, j = 4. nums2[4] = 15. 19 > 15, increment i to 3.
8. i = 3, j = 4. nums1[3] = 5, nums2[4] = 15. 5 <= 15, valid. Distance is 4 - 3 = 1. max_dist remains 1. Increment j to 5.
9. j = 5 is out of bounds, stop.

The answer is 1, which is the largest distance found among all valid pairs.

Time and Space Complexity

• Brute-force approach: For each index i in nums1, you could check every j in nums2 with j >= i, resulting in O(N^2) time complexity. This is inefficient for large input sizes.
• Optimized two-pointer approach: Both pointers only move forward, and each can move at most n times (where n is the length of the larger array). Therefore, the time complexity is O(N).
• Space complexity: Both approaches use only a constant amount of extra space, so the space complexity is O(1).

Summary

The main insight is to use the sorted property of the arrays to efficiently find the maximum distance between valid pairs. By using a two-pointer technique, we avoid redundant checks and achieve a linear-time solution. This approach is both elegant and efficient, making it well-suited for large input sizes. The problem demonstrates how recognizing array properties and choosing the right algorithmic strategy can dramatically improve performance.