Given a sequence of points on a 2D grid, find the minimum time needed to visit them in order when each move can change one or both coordinates by 1.
Problem
You are given an ordered list of points on a 2D grid. Starting from the first point, you must visit every point in the given order.
In one second, you may move from (x, y) to any of the 8 neighboring cells, meaning you can change:
xby at most 1, andyby at most 1.
This means each second you may move horizontally, vertically, or diagonally by one unit.
Return the minimum number of seconds needed to start at the first point and visit all points in order.
Key idea
For two consecutive points, the minimum time is determined by how far apart they are in the horizontal and vertical directions. The answer is the sum of the required time for each consecutive pair.
Input Format
- A list of 2D integer points
points, wherepoints[i] = [x_i, y_i]. - Points must be visited in the given order.
Output Format
- Return a single integer: the minimum total time to visit all points in order.
Constraints
1 <= points.length- Each point contains exactly two integers.
- Coordinates are integers.
- Consecutive points may be equal.
Example 1
Input
points = [[1,1],[3,4],[-1,0]]
Output
7
Explanation
From (1,1) to (3,4), the time is max(|3-1|, |4-1|) = 3. From (3,4) to (-1,0), the time is max(|-1-3|, |0-4|) = 4. Total time = 3 + 4 = 7.
Example 2
Input
points = [[3,2],[-2,2]]
Output
5
Explanation
The horizontal difference is 5 and the vertical difference is 0, so the minimum time is 5.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.