LeetCode 2613 - Beautiful Pairs

The problem asks us to find a beautiful pair of indices (i, j) in two integer arrays nums1 and nums2 of equal length. A pair (i, j) is beautiful if it minimizes the sum of the absolute differences between the corresponding elements: among all possible pairs where i < j.

leetcodehardarraymathdivide-and-conquergeometrysortingordered-set

LeetCode Problem 2613

Difficulty: 🔴 Hard
Topics: Array, Math, Divide and Conquer, Geometry, Sorting, Ordered Set

Solution

Problem Understanding

The problem asks us to find a beautiful pair of indices (i, j) in two integer arrays nums1 and nums2 of equal length. A pair (i, j) is beautiful if it minimizes the sum of the absolute differences between the corresponding elements:

|nums1[i] - nums1[j]| + |nums2[i] - nums2[j]|

among all possible pairs where i < j. If there are multiple pairs with the same minimum value, the lexicographically smallest pair is returned. Lexicographic order means we first compare i, and if those are equal, we compare j.

The input arrays have up to 10^5 elements, which is large enough to make brute-force enumeration of all pairs infeasible, since that would require O(n^2) operations. The values of nums1[i] and nums2[i] are non-negative integers bounded by the length of the arrays.

Important edge cases include arrays where the minimal difference occurs at the very first or last indices, arrays with repeated values, and arrays where all elements are the same. The problem guarantees at least two elements, so we do not need to handle empty arrays.

Approaches

The brute-force approach is straightforward: iterate over all pairs (i, j) with i < j, compute the value |nums1[i] - nums1[j]| + |nums2[i] - nums2[j]| for each pair, and track the pair with the smallest value. This works correctly but requires O(n^2) time, which is not feasible for n up to 10^5.

The key insight for an optimal solution comes from observing that the Manhattan distance formula can be rewritten using sums and differences of coordinates. For any two points (nums1[i], nums2[i]) and (nums1[j], nums2[j]), the Manhattan distance is:

|nums1[i] - nums1[j]| + |nums2[i] - nums2[j]|

This distance is minimized when we consider pairs that are adjacent along sorted transformed coordinates. Specifically, by considering transformations such as nums1[i] + nums2[i] and nums1[i] - nums2[i], and sorting the indices by these values, we only need to check adjacent elements in each sorted order. This reduces the number of candidate pairs dramatically from O(n^2) to O(n) after sorting.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Compute the sum of absolute differences for all pairs
Optimal O(n log n) O(n) Sort transformed coordinates and check adjacent pairs only

Algorithm Walkthrough

  1. Transform coordinates: For each index i, compute four transformed values: nums1[i] + nums2[i], nums1[i] - nums2[i], -nums1[i] + nums2[i], -nums1[i] - nums2[i]. These transformations capture all combinations of signs in the Manhattan distance formula.
  2. Sort indices: For each transformation, sort the indices based on the transformed values.
  3. Check adjacent pairs: For each sorted list of indices, iterate over consecutive pairs (i, j). Compute the original Manhattan distance |nums1[i] - nums1[j]| + |nums2[i] - nums2[j]| and update the minimum distance and the lexicographically smallest pair.
  4. Return result: After considering all four transformations and adjacent pairs, return the pair with the smallest distance. If multiple pairs have the same distance, return the one that is lexicographically smallest.

Why it works: Sorting by the transformed coordinates ensures that the smallest Manhattan distance must occur between adjacent points in at least one transformation. This is a consequence of the Manhattan distance decomposition along the axes. By considering all four transformations, we guarantee that we do not miss the true minimum.

Python Solution

from typing import List

class Solution:
    def beautifulPair(self, nums1: List[int], nums2: List[int]) -> List[int]:
        n = len(nums1)
        min_dist = float('inf')
        result = [0, 1]

        transformations = [
            lambda i: nums1[i] + nums2[i],
            lambda i: nums1[i] - nums2[i],
            lambda i: -nums1[i] + nums2[i],
            lambda i: -nums1[i] - nums2[i]
        ]

        for transform in transformations:
            indices = list(range(n))
            indices.sort(key=transform)
            for k in range(n - 1):
                i, j = indices[k], indices[k + 1]
                dist = abs(nums1[i] - nums1[j]) + abs(nums2[i] - nums2[j])
                if dist < min_dist or (dist == min_dist and [i, j] < result):
                    min_dist = dist
                    result = [i, j]
        return result

Explanation: We iterate over each of the four transformations. Sorting indices by each transformation ensures that minimal distances occur between consecutive indices. We compute the Manhattan distance for each adjacent pair, updating the minimum distance and maintaining lexicographical order. Finally, we return the best pair found.

Go Solution

package main

import (
	"math"
	"sort"
)

func beautifulPair(nums1 []int, nums2 []int) []int {
	n := len(nums1)
	minDist := math.MaxInt64
	result := []int{0, 1}

	transformations := []func(int) int{
		func(i int) int { return nums1[i] + nums2[i] },
		func(i int) int { return nums1[i] - nums2[i] },
		func(i int) int { return -nums1[i] + nums2[i] },
		func(i int) int { return -nums1[i] - nums2[i] },
	}

	for _, transform := range transformations {
		indices := make([]int, n)
		for i := 0; i < n; i++ {
			indices[i] = i
		}
		sort.Slice(indices, func(i, j int) bool {
			return transform(indices[i]) < transform(indices[j])
		})
		for k := 0; k < n-1; k++ {
			i, j := indices[k], indices[k+1]
			dist := abs(nums1[i]-nums1[j]) + abs(nums2[i]-nums2[j])
			if dist < minDist || (dist == minDist && (i < result[0] || (i == result[0] && j < result[1]))) {
				minDist = dist
				result[0], result[1] = i, j
			}
		}
	}
	return result
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

Explanation: The Go solution mirrors the Python version. Slice initialization and sort.Slice are used for sorting indices. Lexicographical comparison is handled explicitly. The abs function is implemented manually since Go lacks a built-in generic abs for integers.

Worked Examples

Example 1: nums1 = [1,2,3,2,4], nums2 = [2,3,1,2,3]

Transformation nums1[i] - nums2[i]: [ -1, -1, 2, 0, 1 ]

Sorted indices: [0,1,3,4,2]

Check adjacent pairs: (0,1)=2, (1,3)=1 (new minimum), (3,4)=1 (not smaller lexicographically), (4,2)=4

Result: [1,3] after checking all transformations. After considering all transformations, final result is [0,3].

Example 2: nums1 = [1,2,4,3,2,5], nums2 = [1,4,2,3,5,1]

Transformation nums1[i] + nums2[i]: [2,6,6,6,7,6]

Sorted indices: [0,1,2,3,5,4]

Check adjacent pairs: (0,1)=5, (1,2)=4, (2,3)=2, (3,5)=3, (5,4)=7

Transformation nums1[i] - nums2[i]: [0,-2,2,0,-3,4]

Sorted indices: [4,1,0,3,2,5]

Check adjacent pairs: (4,1)=1 → new minimum

Result: [1,4]

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting n indices for 4 transformations dominates; adjacent checks are O(n)
Space O(n) Storing index lists for sorting

Sorting four times dominates the runtime, and storing indices requires additional space proportional to n.

Test Cases

# Provided examples
assert Solution().beautifulPair([1,2,3,2,4], [2,3,1,2,3])