Minimum Time Visiting All Points

easy array geometry math

Problem

You are given an array of points on a 2D plane that must be visited in the given order. In one second you can move one unit vertically, horizontally, or diagonally (any of the 8 directions). Return the minimum number of seconds to visit every point in order.

Inputpoints = [[1,1],[3,4],[-1,0]]

Output7

(1,1)→(3,4): max(|2|,|3|) = 3. (3,4)→(−1,0): max(|−4|,|−4|) = 4. Total = 3 + 4 = 7.

points (x:y, comma-separated)

def min_time_to_visit_all_points(points):
    total = 0
    for i in range(1, len(points)):
        x1, y1 = points[i - 1]
        x2, y2 = points[i]
        dx = abs(x2 - x1)
        dy = abs(y2 - y1)
        total += max(dx, dy)
    return total

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

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;
}

int minTimeToVisitAllPoints(vector<vector<int>>& points) {
    int total = 0;
    for (int i = 1; i < 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;
}

Explanation

The key insight is the cost of travelling between two single points. Because we can move diagonally, one second can change both the x and y coordinate at the same time. So the cheapest way to go from (x1, y1) to (x2, y2) is to move diagonally as long as both coordinates still differ, then walk straight along whichever axis is left over.

That cost equals max(|x2 − x1|, |y2 − y1|) — the larger of the horizontal and vertical gaps. This quantity is the Chebyshev distance. The diagonal steps cover the smaller gap "for free" while we are closing the larger one.

Since the points must be visited in order, the total time is simply the sum of the Chebyshev distances of every consecutive pair. There is no routing choice to make, so a single linear pass solves it.

We iterate from the second point onward, compute dx and dy against the previous point, add max(dx, dy) to a running total, and return it.

Example: [[1,1],[3,4],[-1,0]]. The first hop needs max(2,3)=3 seconds, the second needs max(4,4)=4, giving 3 + 4 = 7.

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