Domain 1EasyCORE

Minimum Time Visiting All Points

The problem requires calculating the minimum time needed to visit all given points on a 2D plane in the order they are provided. Each point has integer coordinates `[xi, yi]`. The movement rules allow for vertical, horizontal, or diagonal moves, where diagonal moves cover one unit vertically and one unit horizontally simultaneously.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Geometry

1266. Minimum Time Visiting All Points

Model: qwen2.5-coder:14b
Topics: Array,Geometry
FAANG asked: 1
Acceptance rate: 79.3%


Problem Breakdown

The problem requires calculating the minimum time needed to visit all given points on a 2D plane in the order they are provided. Each point has integer coordinates [xi, yi]. The movement rules allow for vertical, horizontal, or diagonal moves, where diagonal moves cover one unit vertically and one unit horizontally simultaneously.

Inputs:

  • points: A list of lists, where each sublist contains two integers representing the x and y coordinates of a point.

Outputs:

  • An integer representing the minimum time required to visit all points in order.

Implicit Constraints or Tricky Edge Cases:

  • The input list can be empty (though the problem specifies 1 <= n <= 100, so this is unlikely).
  • Points may have duplicate coordinates, meaning a point might need to be visited multiple times.
  • Coordinates can range from -1000 to 1000.

Intuition

A brute-force approach would involve checking all possible paths between consecutive points and calculating the time for each path. However, this is inefficient due to its high time complexity.

The key insight is that moving diagonally covers both vertical and horizontal distances simultaneously when they are equal. Therefore, the minimum time to move from one point to another is determined by the maximum of the absolute differences in their x and y coordinates. This approach ensures that we always take the most efficient path (either diagonal or straight) between points.

Approach

  1. Initialize a variable total_time to zero to keep track of the cumulative time.
  2. Iterate through the list of points, starting from the second point.
  3. For each pair of consecutive points (x1, y1) and (x2, y2), calculate the absolute differences in their x and y coordinates: dx = abs(x2 - x1) and dy = abs(y2 - y1).
  4. The time to move from one point to another is the maximum of dx and dy, as diagonal moves cover both dimensions simultaneously.
  5. Add this time to total_time.
  6. After iterating through all points, return total_time.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of points. We iterate through the list of points once.
  • Space Complexity: O(1). We use a constant amount of extra space regardless of the input size.

Solution

def minTimeToVisitAllPoints(points):
    total_time = 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_time += max(dx, dy)
    return total_time

Edge Cases Handled

  • Empty Input: The function handles an empty input list gracefully by returning 0, as there are no points to visit.
  • Duplicate Points: If a point appears multiple times consecutively, the time between those visits is correctly calculated as zero since dx and dy would both be zero.
  • Negative Coordinates: The use of absolute values ensures that negative coordinates are handled correctly without affecting the calculation of movement time.