LogoKode$word
LeetCode 1855 Maximum Distance Between Pair of Values | Two Pointer Java Solution
LeetCode 1855 Maximum Distance Between Pair of Values | Two Pointer Java Solution

LeetCode 1855 Maximum Distance Between Pair of Values | Two Pointer Java Solution

Learn how to solve LeetCode 1855 using the two-pointer technique. Includes intuition, dry run, optimized Java code, and alternative approaches.

15 views
0
0
Github icon
Github icon
Listen to articleAudio version

Introduction

LeetCode 1855 – Maximum Distance Between a Pair of Values is a classic problem that beautifully demonstrates the power of the Two Pointer technique on sorted (non-increasing) arrays.

At first glance, it may feel like a brute-force problem—but using the right observation, it can be solved efficiently in O(n) time.

In this article, we will cover:

  1. Problem intuition
  2. Why brute force fails
  3. Optimized two-pointer approach (your solution)
  4. Alternative approaches
  5. Time complexity analysis

🔗 Problem Link

LeetCode: Maximum Distance Between a Pair of Values

Problem Statement

You are given two non-increasing arrays:

  1. nums1
  2. nums2

A pair (i, j) is valid if:

  1. i <= j
  2. nums1[i] <= nums2[j]

👉 Distance = j - i

Return the maximum distance among all valid pairs.

Examples

Example 1

Input:

nums1 = [55,30,5,4,2]

nums2 = [100,20,10,10,5]

Output:

2

Key Insight

The most important observation:

Both arrays are NON-INCREASING

👉 This allows us to use two pointers efficiently instead of brute force.

❌ Naive Approach (Brute Force)

Idea

  1. Try all (i, j) pairs
  2. Check conditions
  3. Track maximum

Complexity

  1. Time: O(n × m) ❌

👉 This will cause TLE for large inputs (up to 10⁵)

✅ Optimized Approach: Two Pointers

Intuition

Use two pointers:

i → nums1
j → nums2

We try to:

  1. Expand j as far as possible
  2. Move i only when necessary

Key Logic

If nums1[i] <= nums2[j] → valid → increase j
Else → move i forward

Java Code

class Solution {
public int maxDistance(int[] nums1, int[] nums2) {

int i = 0; // pointer for nums1
int j = 0; // pointer for nums2

int max = Integer.MIN_VALUE;

// Traverse both arrays
while (i < nums1.length && j < nums2.length) {

// Valid pair condition
if (nums1[i] <= nums2[j] && i <= j) {

// Update maximum distance
max = Math.max(max, j - i);

// Try to expand distance by moving j
j++;

} else if (nums1[i] >= nums2[j]) {

// nums1[i] is too large → move i forward
i++;

} else {

// Just move j forward
j++;
}
}

// If no valid pair found, return 0
return max == Integer.MIN_VALUE ? 0 : max;
}
}

Step-by-Step Dry Run

Input:

nums1 = [55,30,5,4,2]
nums2 = [100,20,10,10,5]

Execution:

  1. (0,0) → valid → distance = 0
  2. Move j → (0,1) → invalid → move i
  3. Continue...

Final best pair:

(i = 2, j = 4) → distance = 2

Why This Works

  1. Arrays are sorted (non-increasing)
  2. Moving j increases distance
  3. Moving i helps find valid pairs

👉 No need to re-check previous elements

Complexity Analysis

Time Complexity

  1. O(n + m)

Each pointer moves at most once through the array.

Space Complexity

  1. O(1) (no extra space used)

Alternative Approach: Binary Search

Idea

For each i in nums1:

  1. Use binary search in nums2
  2. Find farthest j such that:
nums2[j] >= nums1[i]

Complexity

  1. O(n log m)

Code (Binary Search Approach)

class Solution {
public int maxDistance(int[] nums1, int[] nums2) {

int max = 0;

for (int i = 0; i < nums1.length; i++) {

int left = i, right = nums2.length - 1;

while (left <= right) {

int mid = left + (right - left) / 2;

if (nums2[mid] >= nums1[i]) {
max = Math.max(max, mid - i);
left = mid + 1;
} else {
right = mid - 1;
}
}
}

return max;
}
}

Two Pointer vs Binary Search

ApproachTimeSpace
Two PointerO(n + m) ✅O(1)
Binary SearchO(n log m)O(1)

👉 Two pointer is optimal here

Key Takeaways

  1. Use two pointers when arrays are sorted
  2. Always look for monotonic properties
  3. Avoid brute force when constraints are large
  4. Greedy pointer movement can optimize drastically

Common Interview Patterns

This problem is related to:

  1. Two pointer problems
  2. Sliding window
  3. Binary search on arrays
  4. Greedy expansion

Conclusion

The Maximum Distance Between a Pair of Values problem is a great example of how recognizing array properties can drastically simplify the solution.

By using the two-pointer technique, we reduce complexity from O(n²) to O(n)—a massive improvement.

Frequently Asked Questions (FAQs)

1. Why do we use two pointers?

Because arrays are sorted, allowing linear traversal.

2. Why not brute force?

It is too slow for large inputs (10⁵).

3. What is the best approach?

👉 Two-pointer approach

Related Articles

LeetCode 496: Next Greater Element I — Java Solution With All Approaches Explained

LeetCode 496: Next Greater Element I — Java Solution With All Approaches Explained

Master the Monotonic Stack Pattern With HashMap Optimization — Step-by-Step Dry Run, Brute Force to O(n) Solution, and Full Complexity Analysis in Java

Read Article
Find Peak Element – Binary Search Explained with Java Solution (LeetCode 162)

Find Peak Element – Binary Search Explained with Java Solution (LeetCode 162)

Learn how to efficiently find a peak element in an array using binary search. This guide explains the problem clearly, builds intuition step-by-step, and walks through multiple approaches with a clean O(log n) solution.

Read Article
Find First and Last Position in Sorted Array – From Brute Force to Binary Search (LeetCode 34)

Find First and Last Position in Sorted Array – From Brute Force to Binary Search (LeetCode 34)

Optimizing from O(n) Linear Scan to O(log n) Binary Search

Read Article
Search in Rotated Sorted Array II – Binary Search with Duplicates Explained (LeetCode 81)

Search in Rotated Sorted Array II – Binary Search with Duplicates Explained (LeetCode 81)

Learn how to search an element in a rotated sorted array that may contain duplicate values. This guide explains the intuition, challenges caused by duplicates, and a clean Java solution using modified binary search.

Read Article
Ai Assistant Kas