Minimum Time Visiting All Points

Problem#

Visit each point in order. From any point you can move diagonally or orthogonally one unit per second. Return the minimum total time.

Examples#

[[1,1],[3,4],[-1,0]] → 7 (3 + 4).
[[3,2],[-2,2]] → 5.

Constraints#

1 <= points.length <= 100.

Approach#

Between two points, the minimum time is the Chebyshev distance max(|dx|, |dy|) (you can chain diagonal moves until one coordinate matches, then go straight).

Solution#

class Solution {
public:
    int minTimeToVisitAllPoints(vector<vector<int>>& points) {
        int total = 0;
        for (int i = 1; i < (int)points.size(); ++i) {
            int dx = abs(points[i][0] - points[i-1][0]);
            int dy = abs(points[i][1] - points[i-1][1]);
            total += max(dx, dy);
        }
        return total;
    }
};

func minTimeToVisitAllPoints(points [][]int) int {
    abs := func(x int) int {
        if x < 0 {
            return -x
        }
        return x
    }
    total := 0
    for i := 1; i < len(points); i++ {
        dx := abs(points[i][0] - points[i-1][0])
        dy := abs(points[i][1] - points[i-1][1])
        if dx > dy {
            total += dx
        } else {
            total += dy
        }
    }
    return total
}

from typing import List

class Solution:
    def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
        total = 0
        for i in range(1, len(points)):
            dx = abs(points[i][0] - points[i - 1][0])
            dy = abs(points[i][1] - points[i - 1][1])
            total += max(dx, dy)
        return total

function minTimeToVisitAllPoints(points) {
    let total = 0;
    for (let i = 1; i < points.length; i++) {
        const dx = Math.abs(points[i][0] - points[i - 1][0]);
        const dy = Math.abs(points[i][1] - points[i - 1][1]);
        total += Math.max(dx, dy);
    }
    return total;
}

class Solution {
    public int minTimeToVisitAllPoints(int[][] points) {
        int total = 0;
        for (int i = 1; i < points.length; i++) {
            int dx = Math.abs(points[i][0] - points[i - 1][0]);
            int dy = Math.abs(points[i][1] - points[i - 1][1]);
            total += Math.max(dx, dy);
        }
        return total;
    }
}

function minTimeToVisitAllPoints(points: number[][]): number {
    let total = 0;
    for (let i = 1; i < points.length; i++) {
        const dx = Math.abs(points[i][0] - points[i - 1][0]);
        const dy = Math.abs(points[i][1] - points[i - 1][1]);
        total += Math.max(dx, dy);
    }
    return total;
}

Editorial#

With unit diagonal moves allowed (Chebyshev/king-move), the shortest path between two grid points is governed by the larger coordinate-delta. The total just sums these consecutive Chebyshev distances along the visiting order.

Complexity#

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

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#