#1266

Easy

LeetCode Problem Workspace

Minimum Time Visiting All Points

Calculate the minimum seconds required to visit all given 2D points in order using optimal diagonal or straight moves.

Problem Statement

You are given a list of n points on a 2D plane with integer coordinates points[i] = [xi, yi]. Starting at the first point, you must visit all points in the order given. At each step, you can move horizontally, vertically, or diagonally by 1 unit per second. Return the minimum total time in seconds to visit all points in order.

Movement rules allow diagonal moves that change both coordinates simultaneously by 1 unit, or straight moves along one axis by 1 unit per second. For example, moving from [1,1] to [3,4] can combine diagonal steps and straight steps to minimize time, demonstrating the array plus math pattern of calculating max differences between coordinates.

Examples

Example 1

Input: points = [[1,1],[3,4],[-1,0]]

Output: 7

One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0] Time from [1,1] to [3,4] = 3 seconds Time from [3,4] to [-1,0] = 4 seconds Total time = 7 seconds

Example 2

Input: points = [[3,2],[-2,2]]

Output: 5

Example details omitted.

Constraints

points.length == n
1 <= n <= 100
points[i].length == 2
-1000 <= points[i][0], points[i][1] <= 1000

Solution Approach

Iterate Consecutive Points

Loop through each consecutive pair of points in the array, calculating the horizontal difference dx and vertical difference dy between them. This approach directly reflects the Array plus Math pattern by treating point pairs as array elements and computing numeric distances.

Compute Optimal Move Time

For each pair, the minimum time is max(dx, dy) because diagonal moves reduce both coordinates simultaneously. This avoids overcounting steps along one axis and ensures that the total is minimized, which is the core math insight in this problem.

Sum Times for Total

Accumulate the max(dx, dy) for all consecutive pairs to get the total minimum time. This maintains O(n) time and O(1) space, staying efficient and aligned with the problem's expected solution pattern.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Time complexity is O(n) since each point pair is visited once. Space complexity is O(1) because no extra data structures proportional to n are used, only scalar accumulators.

What Interviewers Usually Probe

You may be asked to justify why diagonal moves are always optimal between two points.
Clarify the relationship between horizontal and vertical distances for move counting.
Expect questions linking array iteration with distance calculation, highlighting the Array plus Math pattern.

Common Pitfalls or Variants

Common pitfalls

Counting horizontal and vertical moves separately instead of using max(dx, dy) leads to overestimating time.
Ignoring diagonal moves can make solutions longer and fail efficiency expectations.
Off-by-one errors in computing differences between coordinates may cause incorrect totals.

Follow-up variants

Allowing arbitrary order traversal changes the problem into a minimum path or traveling salesman variant.
Restricting diagonal moves to only certain directions increases complexity and requires conditional logic.
Expanding to 3D coordinates introduces an extra axis, still solvable with max differences but with three dimensions.

FAQ

How does the maximum of horizontal and vertical distances determine move time?

Using max(dx, dy) captures the optimal combination of diagonal and straight moves, minimizing seconds for each point pair.

Can I use only horizontal and vertical moves to solve this problem?

Yes, but it will overcount steps; diagonal moves reduce total time and are key to the minimal time solution.

What pattern does this problem represent in algorithms?

It follows the Array plus Math pattern, where array iteration is combined with simple coordinate arithmetic to compute results efficiently.

Does the solution scale for large arrays of points?

Yes, it runs in O(n) time and O(1) space, making it efficient for up to 100 points as per constraints.

How do I verify the output for points = [[1,1],[3,4],[-1,0]]?

Compute max differences for each consecutive pair: [1,1]->[3,4] gives 3, [3,4]->[-1,0] gives 4; sum to get total time 7 seconds.

terminal

Solution

Solution 1: Simulation

For two points $p_1=(x_1, y_1)$ and $p_2=(x_2, y_2)$, the distances moved in the horizontal and vertical directions are $d_x = |x_1 - x_2|$ and $d_y = |y_1 - y_2|$ respectively.

1

2

3

4

5

class Solution:
    def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
        return sum(
            max(abs(p1[0] - p2[0]), abs(p1[1] - p2[1])) for p1, p2 in pairwise(points)
        )

Continue Practicing

#1232 check if it is a straight line #1453 maximum number of darts inside of a circular dartboard #1037 valid boomerang