Leetcode 1855. Maximum Distance Between a Pair of Values

Problem Explanation

You are given two non-increasing arrays nums1 and nums2. Your task is to find the maximum distance between the indices (i, j) such that i <= j and nums1[i] <= nums2[j]. If there are no such valid pairs, return 0.

Approach

The approach used in the solution is called "Two Pointers". We will start with two pointers i and j, both initially at 0. Iterate through the arrays, comparing the elements at the current indices and updating the pointers accordingly. If nums1[i] > nums2[j], we need to increment pointer i; otherwise, update the maximum distance with j - i and increment pointer j. Finally, we will return the maximum distance found.

Walkthrough

Let's go through an example to understand the solution better.

Consider the following inputs: nums1 = [30, 29, 19, 5] nums2 = [25, 25, 25, 25, 25]

We will start with pointers i = 0, j = 0. At each iteration:

1. nums1[0] = 30, nums2[0] = 25, nums1[i] > nums2[j], so we increment i to 1.
2. nums1[1] = 29, nums2[0] = 25, nums1[i] > nums2[j], so we increment i to 2.
3. nums1[2] = 19, nums2[0] = 25, nums1[i] <= nums2[j], so we update the maximum distance (currently 0) with j - i (0 - 2) = -2, and increment j to 1. As the maximum distance cannot be negative, it remains 0.
4. nums1[2] = 19, nums2[1] = 25, nums1[i] <= nums2[j], so we update the maximum distance (currently 0) with j - i (1 - 2) = -1, and increment j to 2. As the maximum distance cannot be negative, it remains 0.
5. nums1[2] = 19, nums2[2] = 25, nums1[i] <= nums2[j], so we update the maximum distance (currently 0) with j - i (2 - 2) = 0, and increment j to 3.
6. nums1[2] = 19, nums2[3] = 25, nums1[i] <= nums2[j], so we update the maximum distance (currently 0) with j - i (3 - 2) = 1, and increment j to 4.
7. nums1[2] = 19, nums2[4] = 25, nums1[i] <= nums2[j], so we update the maximum distance (currently 1) with j - i (4 - 2) = 2, and increment j to 5. As j >= nums2.length, we break the loop.

The final answer is the maximum distance found, which is 2 in this case.

Now, let's write the solutions in multiple programming languages.

Python Solution

1class Solution:
2    def maxDistance(self, nums1: List[int], nums2: List[int]) -> int:
3        ans = 0
4        i = 0
5        j = 0
6
7        while i < len(nums1) and j < len(nums2):
8            if nums1[i] > nums2[j]:
9                i += 1
10            else:
11                ans = max(ans, j - i)
12                j += 1
13
14        return ans

Java Solution

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

JavaScript Solution

1class Solution {
2    maxDistance(nums1, nums2) {
3        let ans = 0;
4        let i = 0;
5        let j = 0;
6
7        while (i < nums1.length && j < nums2.length) {
8            if (nums1[i] > nums2[j]) {
9                i++;
10            } else {
11                ans = Math.max(ans, j - i);
12                j++;
13            }
14        }
15        return ans;
16    }
17}

C++ Solution

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

C# Solution

1public class Solution {
2    public int MaxDistance(int[] nums1, int[] nums2) {
3        int ans = 0;
4        int i = 0;
5        int j = 0;
6
7        while (i < nums1.Length && j < nums2.Length) {
8            if (nums1[i] > nums2[j]) {
9                i++;
10            } else {
11                ans = Math.Max(ans, j - i);
12                j++;
13            }
14        }
15        return ans;
16    }
17}

In each of the solutions above, we followed the algorithm explained earlier, using two pointers to traverse the arrays and update the maximum distance.## Time Complexity

The time complexity of this solution is O(n), where n is the maximum length of the input arrays. This is because we traverse the arrays once using two pointers, which increment in non-decreasing order and do not go back. The result is a single pass algorithm with a linear time complexity.

Space Complexity

The space complexity of the given solution is O(1). This is because only a constant amount of additional space is used for storing variables and pointers, and no additional data structures are used in any of the solutions. This makes the algorithm highly space-efficient.