Minimize Manhattan Distances

Problem#

Given points, the “distance” of the set is the maximum Manhattan distance between any two. Remove exactly one point to minimize this distance and return the new value.

Examples#

[[3,10],[5,15],[10,2],[4,4]] → 12.
[[1,1],[1,1],[1,1]] → 0.

Constraints#

3 <= points.length <= 10^5.

Approach#

In rotated coords (u,v) = (x+y, x-y), Manhattan distance equals Chebyshev = max(|du|, |dv|). The max distance is max(maxU - minU, maxV - minV). We need top-2 max and bottom-2 min of u and v so removing any point lets us fall back to the secondary extremes.

Solution#

class Solution {
public:
    int minimumDistance(vector<vector<int>>& points) {
        int n = points.size();
        multiset<int> us, vs;
        for (auto& p : points) {
            us.insert(p[0] + p[1]);
            vs.insert(p[0] - p[1]);
        }
        int ans = INT_MAX;
        for (auto& p : points) {
            int u = p[0] + p[1], v = p[0] - p[1];
            us.erase(us.find(u));
            vs.erase(vs.find(v));
            int d = max(*us.rbegin() - *us.begin(), *vs.rbegin() - *vs.begin());
            ans = min(ans, d);
            us.insert(u);
            vs.insert(v);
        }
        return ans;
    }
};

import "math"

func minimumDistance(points [][]int) int {
    n := len(points)
    us := make([]int, n)
    vs := make([]int, n)
    for i, p := range points {
        us[i] = p[0] + p[1]
        vs[i] = p[0] - p[1]
    }
    // Find top-2 max and bottom-2 min indices for u and v.
    findTop2Max := func(a []int) (int, int) {
        i1, i2 := -1, -1
        for i := 0; i < len(a); i++ {
            if i1 < 0 || a[i] > a[i1] {
                i2 = i1
                i1 = i
            } else if i2 < 0 || a[i] > a[i2] {
                i2 = i
            }
        }
        return i1, i2
    }
    findTop2Min := func(a []int) (int, int) {
        i1, i2 := -1, -1
        for i := 0; i < len(a); i++ {
            if i1 < 0 || a[i] < a[i1] {
                i2 = i1
                i1 = i
            } else if i2 < 0 || a[i] < a[i2] {
                i2 = i
            }
        }
        return i1, i2
    }
    uMax1, uMax2 := findTop2Max(us)
    uMin1, uMin2 := findTop2Min(us)
    vMax1, vMax2 := findTop2Max(vs)
    vMin1, vMin2 := findTop2Min(vs)
    pick := func(skip, i1, i2 int, a []int) int {
        if skip == i1 {
            return a[i2]
        }
        return a[i1]
    }
    ans := math.MaxInt32
    for i := 0; i < n; i++ {
        uHi := pick(i, uMax1, uMax2, us)
        uLo := pick(i, uMin1, uMin2, us)
        vHi := pick(i, vMax1, vMax2, vs)
        vLo := pick(i, vMin1, vMin2, vs)
        d := uHi - uLo
        if vHi-vLo > d {
            d = vHi - vLo
        }
        if d < ans {
            ans = d
        }
    }
    return ans
}

from typing import List, Tuple

class Solution:
    def minimumDistance(self, points: List[List[int]]) -> int:
        n = len(points)
        us = [p[0] + p[1] for p in points]
        vs = [p[0] - p[1] for p in points]

        def find_top2_max(a: List[int]) -> Tuple[int, int]:
            i1, i2 = -1, -1
            for i in range(len(a)):
                if i1 < 0 or a[i] > a[i1]:
                    i2 = i1
                    i1 = i
                elif i2 < 0 or a[i] > a[i2]:
                    i2 = i
            return i1, i2

        def find_top2_min(a: List[int]) -> Tuple[int, int]:
            i1, i2 = -1, -1
            for i in range(len(a)):
                if i1 < 0 or a[i] < a[i1]:
                    i2 = i1
                    i1 = i
                elif i2 < 0 or a[i] < a[i2]:
                    i2 = i
            return i1, i2

        uMax1, uMax2 = find_top2_max(us)
        uMin1, uMin2 = find_top2_min(us)
        vMax1, vMax2 = find_top2_max(vs)
        vMin1, vMin2 = find_top2_min(vs)

        def pick(skip: int, i1: int, i2: int, a: List[int]) -> int:
            return a[i2] if skip == i1 else a[i1]

        ans = float('inf')
        for i in range(n):
            uHi = pick(i, uMax1, uMax2, us)
            uLo = pick(i, uMin1, uMin2, us)
            vHi = pick(i, vMax1, vMax2, vs)
            vLo = pick(i, vMin1, vMin2, vs)
            d = max(uHi - uLo, vHi - vLo)
            if d < ans:
                ans = d
        return int(ans)

function minimumDistance(points) {
    const n = points.length;
    const us = new Array(n);
    const vs = new Array(n);
    for (let i = 0; i < n; i++) {
        us[i] = points[i][0] + points[i][1];
        vs[i] = points[i][0] - points[i][1];
    }
    const findTop2Max = (a) => {
        let i1 = -1, i2 = -1;
        for (let i = 0; i < a.length; i++) {
            if (i1 < 0 || a[i] > a[i1]) { i2 = i1; i1 = i; }
            else if (i2 < 0 || a[i] > a[i2]) { i2 = i; }
        }
        return [i1, i2];
    };
    const findTop2Min = (a) => {
        let i1 = -1, i2 = -1;
        for (let i = 0; i < a.length; i++) {
            if (i1 < 0 || a[i] < a[i1]) { i2 = i1; i1 = i; }
            else if (i2 < 0 || a[i] < a[i2]) { i2 = i; }
        }
        return [i1, i2];
    };
    const [uMax1, uMax2] = findTop2Max(us);
    const [uMin1, uMin2] = findTop2Min(us);
    const [vMax1, vMax2] = findTop2Max(vs);
    const [vMin1, vMin2] = findTop2Min(vs);
    const pick = (skip, i1, i2, a) => skip === i1 ? a[i2] : a[i1];
    let ans = Infinity;
    for (let i = 0; i < n; i++) {
        const uHi = pick(i, uMax1, uMax2, us);
        const uLo = pick(i, uMin1, uMin2, us);
        const vHi = pick(i, vMax1, vMax2, vs);
        const vLo = pick(i, vMin1, vMin2, vs);
        const d = Math.max(uHi - uLo, vHi - vLo);
        if (d < ans) ans = d;
    }
    return ans;
}

class Solution {
    public int minimumDistance(int[][] points) {
        int n = points.length;
        int[] us = new int[n];
        int[] vs = new int[n];
        for (int i = 0; i < n; i++) {
            us[i] = points[i][0] + points[i][1];
            vs[i] = points[i][0] - points[i][1];
        }
        int[] uMax = findTop2Max(us);
        int[] uMin = findTop2Min(us);
        int[] vMax = findTop2Max(vs);
        int[] vMin = findTop2Min(vs);
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int uHi = pick(i, uMax[0], uMax[1], us);
            int uLo = pick(i, uMin[0], uMin[1], us);
            int vHi = pick(i, vMax[0], vMax[1], vs);
            int vLo = pick(i, vMin[0], vMin[1], vs);
            int d = Math.max(uHi - uLo, vHi - vLo);
            if (d < ans) ans = d;
        }
        return ans;
    }

    private int[] findTop2Max(int[] a) {
        int i1 = -1, i2 = -1;
        for (int i = 0; i < a.length; i++) {
            if (i1 < 0 || a[i] > a[i1]) { i2 = i1; i1 = i; }
            else if (i2 < 0 || a[i] > a[i2]) { i2 = i; }
        }
        return new int[]{i1, i2};
    }

    private int[] findTop2Min(int[] a) {
        int i1 = -1, i2 = -1;
        for (int i = 0; i < a.length; i++) {
            if (i1 < 0 || a[i] < a[i1]) { i2 = i1; i1 = i; }
            else if (i2 < 0 || a[i] < a[i2]) { i2 = i; }
        }
        return new int[]{i1, i2};
    }

    private int pick(int skip, int i1, int i2, int[] a) {
        return skip == i1 ? a[i2] : a[i1];
    }
}

function minimumDistance(points: number[][]): number {
    const n = points.length;
    const us: number[] = new Array(n);
    const vs: number[] = new Array(n);
    for (let i = 0; i < n; i++) {
        us[i] = points[i][0] + points[i][1];
        vs[i] = points[i][0] - points[i][1];
    }
    const findTop2Max = (a: number[]): [number, number] => {
        let i1 = -1, i2 = -1;
        for (let i = 0; i < a.length; i++) {
            if (i1 < 0 || a[i] > a[i1]) { i2 = i1; i1 = i; }
            else if (i2 < 0 || a[i] > a[i2]) { i2 = i; }
        }
        return [i1, i2];
    };
    const findTop2Min = (a: number[]): [number, number] => {
        let i1 = -1, i2 = -1;
        for (let i = 0; i < a.length; i++) {
            if (i1 < 0 || a[i] < a[i1]) { i2 = i1; i1 = i; }
            else if (i2 < 0 || a[i] < a[i2]) { i2 = i; }
        }
        return [i1, i2];
    };
    const [uMax1, uMax2] = findTop2Max(us);
    const [uMin1, uMin2] = findTop2Min(us);
    const [vMax1, vMax2] = findTop2Max(vs);
    const [vMin1, vMin2] = findTop2Min(vs);
    const pick = (skip: number, i1: number, i2: number, a: number[]): number =>
        skip === i1 ? a[i2] : a[i1];
    let ans = Infinity;
    for (let i = 0; i < n; i++) {
        const uHi = pick(i, uMax1, uMax2, us);
        const uLo = pick(i, uMin1, uMin2, us);
        const vHi = pick(i, vMax1, vMax2, vs);
        const vLo = pick(i, vMin1, vMin2, vs);
        const d = Math.max(uHi - uLo, vHi - vLo);
        if (d < ans) ans = d;
    }
    return ans;
}

Editorial#

The 45-degree rotation (u,v) = (x+y, x-y) turns L1 into L∞ — a textbook trick. Multisets let us remove a point’s contribution in O(log n) and re-query the new min/max instantly. Constant-factor tighter solutions exist (precompute top-2 extremes), but the multiset version is robust and easy to get right.

Complexity#

Time: O(n log n).
Space: O(n).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#