Maximum Distance Between a Pair of Values

Maximum Distance Between a Pair of Values - 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 the maximum distance of any valid pair (i, j). If there are no valid pairs, return 0.

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

Input & Output

Example 1 — Basic Case

$ Input: nums1 = [55,30,5], nums2 = [100,20,10,5]

› Output: 1

💡 Note: The valid pairs are (0,0), (2,2), and (2,3). The pair (2,3) has the maximum distance of 3-2=1.

Example 2 — No Valid Pairs

$ Input: nums1 = [30,29,19,5], nums2 = [25,25,25,25,25]

› Output: 2

💡 Note: Valid pairs are (3,3) and (3,4). The maximum distance is 4-3=1. Actually, (3,3) gives 0 and (3,4) gives 1, but we also have (2,4) since 19≤25, giving distance 2.

Example 3 — Single Elements

$ Input: nums1 = [1], nums2 = [1]

› Output: 0

💡 Note: Only one valid pair (0,0) with distance 0-0=0.

Constraints

1 ≤ nums1.length, nums2.length ≤ 10⁵
1 ≤ nums1[i], nums2[i] ≤ 10⁵
nums1 and nums2 are non-increasing

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two non-increasing arrays nums1 and nums2

Valid Pairs

Find pairs (i,j) where i≤j and nums1[i]≤nums2[j]

Maximum Distance

Return the largest j-i value found

Key Takeaway

🎯 Key Insight: Use the sorted property to efficiently find pairs without checking all combinations

Asked in

a Amazon 15 M Microsoft 12 G Google 8

The key insight is leveraging the non-increasing property of both arrays. The optimal two pointers approach starts from opposite ends and moves strategically based on the comparison. Time: O(n+m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers	O(n+m)	O(1)	Use two pointers to efficiently find maximum distance by leveraging sorted property
Brute Force	O(n×m)	O(1)	Check all possible pairs (i,j) and find maximum valid distance

Two Pointers — Algorithm Steps

Start with i=0 (nums1) and j=nums2.length-1
If nums1[i] <= nums2[j], we found a valid pair, update max distance and move i forward
Otherwise, move j backward to find a larger value in nums2
Continue until pointers meet

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with i=0 at beginning of nums1, j=3 at end of nums2

Move Pointers

Check conditions and move pointers based on comparison results

Find Maximum

Track maximum distance found during traversal

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int maxDistance = 0;
    int i = 0;
    int j = nums2Size - 1;
    
    while (i < nums1Size && j >= 0) {
        if (i <= j && nums1[i] <= nums2[j]) {
            int distance = j - i;
            if (distance > maxDistance) {
                maxDistance = distance;
            }
            i++;
        } else {
            j--;
        }
    }
    
    return maxDistance;
}

int main() {
    char line[1000];
    int nums1[1000], nums2[1000];
    int nums1Size = 0, nums2Size = 0;
    
    // Parse first array
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] != '\n' && token[0] != ' ' && token[0] != ']') {
            nums1[nums1Size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    // Parse second array
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] != '\n' && token[0] != ' ' && token[0] != ']') {
            nums2[nums2Size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(nums1, nums1Size, nums2, nums2Size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n+m)

Each pointer moves at most n or m times, single pass through both arrays

✓ Linear Growth

Space Complexity

O(1)

Only using two pointer variables and max distance tracker

✓ Linear Space

18.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler