Minimum Time Visiting All Points

Difficulty: Easy | Acceptance: 84.80% | Paid: No Topics: Array, Math, Geometry

On a plane there are n points with integer coordinates points[i] = [xi, yi]. Your task is to find the minimum time in seconds to visit all points.

You can move according to the next rules:

• In one second you can move:
  • vertically by 1 unit,
  • horizontally by 1 unit,
  • diagonally by sqrt(2) units (in other words, move one unit vertically then one unit horizontally in 1 second).
• You have to visit the points in the same order as they appear in the array.
• You are allowed to pass through points that appear later in the order, but only visiting them counts towards the goal.

• Examples
• Constraints
• Mathematical Approach (Chebyshev Distance)
• Simulation Approach

Examples

Example 1:

Input: points = [[1,1],[3,4],[-1,0]]
Output: 7
Explanation:
One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]
Total time 7.

Example 2:

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

Constraints

2 <= points.length <= 1000
points[i].length == 2
-10⁴ <= xi, yi <= 10⁴
All points are distinct.

Mathematical Approach (Chebyshev Distance)

Intuition The minimum time to move from point A to point B is determined by the Chebyshev distance. Since diagonal movement covers both horizontal and vertical distance simultaneously, the time required is the maximum of the horizontal distance and the vertical distance.

Steps

• Initialize a variable time to 0.
• Iterate through the points array from the first point to the second-to-last point.
• For each pair of consecutive points (x1, y1) and (x2, y2):
  • Calculate the absolute difference in x-coordinates: dx = abs(x2 - x1).
  • Calculate the absolute difference in y-coordinates: dy = abs(y2 - y1).
  • Add the maximum of dx and dy to time.
• Return time.

from typing import List

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

Complexity

• Time: O(N), where N is the number of points. We iterate through the list once.
• Space: O(1), we only use a few variables for calculation.
• Notes: This is the optimal solution for this problem.

Simulation Approach

Intuition Simulate the movement step-by-step. At each second, move diagonally towards the target if possible, otherwise move horizontally or vertically. This approach directly implements the movement rules.

Steps

• Initialize time to 0 and set current position to the first point.
• Iterate through the remaining points as targets.
• While the current position is not the target:
  • Determine the direction of movement for x and y axes (-1, 0, or 1).
  • Update the current position.
  • Increment time.
• Return time.

from typing import List

class Solution:
    def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
        time = 0
        cx, cy = points[0]
        for tx, ty in points[1:]:
            while cx != tx or cy != ty:
                dx = tx - cx
                dy = ty - cy
                sx = 0 if dx == 0 else (1 if dx > 0 else -1)
                sy = 0 if dy == 0 else (1 if dy > 0 else -1)
                cx += sx
                cy += sy
                time += 1
        return time

Complexity

• Time: O(N * K), where N is the number of points and K is the maximum distance between any two points. In the worst case, K can be up to 2 * 10⁴.
• Space: O(1), only a few variables are used.
• Notes: While this approach is intuitive, it is less efficient than the mathematical approach for large distances.