2613. Beautiful Pairs

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.

class Solution {
public:
    vector<int> beautifulPair(vector<int>& A, vector<int>& B) {
        map<int, map<int, int>> mp;
        vector<int> res{INT_MAX, INT_MAX};
        int dist = INT_MAX / 2;
        auto chmin = [&](int i, int j) {
            int now = abs(A[i] - A[j]) + abs(B[i] - B[j]);
            if(dist == now) res = min(res, {min(i,j),max(i,j)});
            else if(dist > now) {
                dist = now;
                res = {min(i,j), max(i,j)};
            }
        };
        for(int i = A.size() - 1; i >= 0; i--) {
            int a = A[i], b = B[i];
            auto lo = mp.lower_bound(a - dist);
            auto hi = mp.upper_bound(a + dist);
            for(auto it = lo; it != hi; it++) {
                auto itt = it->second.lower_bound(b);
                if(itt != end(it->second)) chmin(i,itt->second);
                if(itt != begin(it->second)) chmin(i, prev(itt)->second);
            }

            mp[a][b] = i;
        }
        return res;
    }
};