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:
- nums1[0] = 30, nums2[0] = 25, nums1[i] > nums2[j], so we increment i to 1.
- nums1[1] = 29, nums2[0] = 25, nums1[i] > nums2[j], so we increment i to 2.
- 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.
- 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.
- 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.
- 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.
- 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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.