Beautiful Pairs — LeetCode 2613 Python Solution
HardLeetCode PremiumGeometryArrayMathDivide and ConquerOrdered SetSorting
- Problem
- #2613
- Pattern
- Sorting
- Reading time
- 6 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- nums1 = [1,2,3,2,4], nums2 = [2,3,1,2,3]
- Output
- [0,3]
- Explanation
- Consider index 0 and index 3. The value of |nums1[i]-nums1[j]| + |nums2[i]-nums2[j]| is 1, which is the smallest value we can achieve.
Python solution
Python
class Solution:
def beautifulPair(self, nums1: List[int], nums2: List[int]) -> List[int]:
def dist(x1: int, y1: int, x2: int, y2: int) -> int:
return abs(x1 - x2) + abs(y1 - y2)
def dfs(l: int, r: int):
if l >= r:
return inf, -1, -1
m = (l + r) >> 1
x = points[m][0]
d1, pi1, pj1 = dfs(l, m)
d2, pi2, pj2 = dfs(m + 1, r)
if d1 > d2 or (d1 == d2 and (pi1 > pi2 or (pi1 == pi2 and pj1 > pj2))):
d1, pi1, pj1 = d2, pi2, pj2
t = [p for p in points[l : r + 1] if abs(p[0] - x) <= d1]
t.sort(key=lambda x: x[1])
for i in range(len(t)):
for j in range(i + 1, len(t)):
if t[j][1] - t[i][1] > d1:
break
pi, pj = sorted([t[i][2], t[j][2]])
d = dist(t[i][0], t[i][1], t[j][0], t[j][1])
if d < d1 or (d == d1 and (pi < pi1 or (pi == pi1 and pj < pj1))):
d1, pi1, pj1 = d, pi, pj
return d1, pi1, pj1
pl = defaultdict(list)
for i, (x, y) in enumerate(zip(nums1, nums2)):
pl[(x, y)].append(i)
points = []
for i, (x, y) in enumerate(zip(nums1, nums2)):
if len(pl[(x, y)]) > 1:
return [i, pl[(x, y)][1]]
points.append((x, y, i))
points.sort()
_, pi, pj = dfs(0, len(points) - 1)
return [pi, pj]Complexity
| Measure | Complexity |
|---|---|
| Time | O(n log n) |
| Space | O(1) to O(n) auxiliary |
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 2613. Beautiful Pairs is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2613. Beautiful Pairs?
- LeetCode 2613. Beautiful Pairs is rated Hard on LeetCode.
- What topics does LeetCode 2613. Beautiful Pairs cover?
- LeetCode 2613. Beautiful Pairs is tagged Geometry, Array, Math, Divide and Conquer, Ordered Set and Sorting on LeetCode.
- Is LeetCode 2613. Beautiful Pairs a premium problem?
- Yes. LeetCode 2613. Beautiful Pairs is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.