Beautiful Pairs - Practice Coding Problems

Beautiful Pairs - Problem

Array Math Divide and Conquer Geometry Sorting Ordered Set Hard

You are given two 0-indexed integer arrays nums1 and nums2 of the same length.

A pair of indices (i,j) is called beautiful if |nums1[i] - nums1[j]| + |nums2[i] - nums2[j]| is the smallest amongst all possible indices pairs where i < j.

Return the beautiful pair. In the case that there are multiple beautiful pairs, return the lexicographically smallest pair.

Note that |x| denotes the absolute value of x.

A pair of indices (i1, j1) is lexicographically smaller than (i2, j2) if i1 < i2 or i1 == i2 and j1 < j2.

Input & Output

Example 1 — Basic Case

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

› Output: [1,2]

💡 Note: Check all pairs: (0,1) has distance |1-3| + |1-2| = 3, (0,2) has distance |1-2| + |1-3| = 3, (1,2) has distance |3-2| + |2-3| = 2. The minimum distance is 2 at indices (1,2).

Example 2 — Multiple Minimum Pairs

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

› Output: [0,1]

💡 Note: All points are identical, so all pairs have distance 0. Return the lexicographically smallest pair (0,1).

Example 3 — Negative Numbers

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

› Output: [0,1]

💡 Note: Only one pair (0,1) with distance |-1-2| + |1-(-1)| = 3 + 2 = 5.

Constraints

2 ≤ nums1.length == nums2.length ≤ 10⁵
-10⁴ ≤ nums1[i], nums2[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Two arrays representing points in 2D space

Calculate

Find Manhattan distance for each pair

Output

Return lexicographically smallest minimum pair

Key Takeaway

🎯 Key Insight: This is a closest pair problem using Manhattan distance in 2D space

Asked in

G Google 45 f Facebook 32 a Amazon 28

The key insight is recognizing this as a closest pair problem using Manhattan distance. The brute force approach checks all pairs in O(n²) time. The optimized approach uses sorting and geometric properties to prune impossible candidates, improving average case performance. Best approach depends on input size - brute force for small inputs, optimized for larger ones. Time: O(n²), Space: O(1) for brute force.

Common Approaches

Approach	Time	Space	Notes
✓ Sort and Sweep	O(n² log n)	O(n)	Sort points and use geometric properties to reduce unnecessary comparisons
Brute Force	O(n²)	O(1)	Check every possible pair and find the one with minimum Manhattan distance

Sort and Sweep — Algorithm Steps

Create array of points with indices
Sort by first coordinate
For each point, only check nearby points within current minimum distance

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Points

Sort by x-coordinate with original indices

Sweep with Pruning

Skip pairs where x-distance alone exceeds minimum

Update Minimum

Track lexicographically smallest result

Code -

solution.c — C

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

typedef struct {
    int x, y, idx;
} Point;

int comparePoints(const void* a, const void* b) {
    Point* p1 = (Point*)a;
    Point* p2 = (Point*)b;
    return p1->x - p2->x;
}

void solution(int* nums1, int* nums2, int n, int* result) {
    Point points[n];
    for (int i = 0; i < n; i++) {
        points[i].x = nums1[i];
        points[i].y = nums2[i];
        points[i].idx = i;
    }
    
    qsort(points, n, sizeof(Point), comparePoints);
    
    int minDist = INT_MAX;
    result[0] = 0;
    result[1] = 1;
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (points[j].x - points[i].x >= minDist) break;
            
            int dist = abs(points[i].x - points[j].x) + abs(points[i].y - points[j].y);
            int idx1 = points[i].idx < points[j].idx ? points[i].idx : points[j].idx;
            int idx2 = points[i].idx > points[j].idx ? points[i].idx : points[j].idx;
            
            if (dist < minDist || (dist == minDist && (idx1 < result[0] || (idx1 == result[0] && idx2 < result[1])))) {
                minDist = dist;
                result[0] = idx1;
                result[1] = idx2;
            }
        }
    }
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums1[100], nums2[100], n = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        nums1[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    int m = 0;
    token = strtok(line + 1, ",]");
    while (token) {
        nums2[m++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result[2];
    solution(nums1, nums2, n, result);
    printf("[%d,%d]\n", result[0], result[1]);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² log n)

Sorting takes O(n log n), but still need to check pairs in worst case O(n²)

⚠ Quadratic Growth

Space Complexity

O(n)

Extra array to store points with original indices

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 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

Sort and Sweep — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler