On a 2D plane, there are n points with integer coordinates points[i] = [xi, yi]. Return the minimum time in seconds to visit all the points in the order given by points.
You can move according to these rules:
1 second, you can either:
sqrt(2) units (in other words, move one unit vertically then one unit horizontally in 1 second).
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] 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
Constraints:
points.length == n1 <= n <= 100points[i].length == 2-1000 <= points[i][0], points[i][1] <= 1000Problem Overview: You are given an ordered list of 2D points. Starting at the first point, you must visit every next point in sequence. In one second you can move horizontally, vertically, or diagonally. The task is to compute the minimum time required to travel through all points.
The key observation is that a diagonal move changes both x and y simultaneously. This means you should take as many diagonal steps as possible before finishing with horizontal or vertical moves.
Approach 1: Calculate Sum of Step-wise Distances (Simulation) (Time: O(n), Space: O(1))
Process each consecutive pair of points and simulate movement step by step. At each step, move diagonally while both coordinates differ. Once either the x or y coordinate matches the target, continue moving horizontally or vertically until you reach the point. For a pair of points (x1, y1) and (x2, y2), the number of diagonal steps equals min(|x2-x1|, |y2-y1|). The remaining difference is covered with straight moves.
This method reflects the physical movement rules and makes the reasoning easy to follow. You iterate through the array of points, calculate coordinate differences, and accumulate the required steps. Even though the logic mimics movement, the total steps simplify mathematically.
Approach 2: Calculate Maximum of X and Y Differences (Chebyshev Distance) (Time: O(n), Space: O(1))
The optimal insight comes from geometry. When diagonal movement is allowed, the shortest path between two grid points equals the Chebyshev distance. For points (x1, y1) and (x2, y2), the minimum number of seconds required is max(|x2 - x1|, |y2 - y1|). Diagonal moves reduce both coordinate differences simultaneously, so the larger difference determines the total time.
Iterate once through the points and compute this value for each consecutive pair. Add the result to a running total. This avoids simulating movement and directly computes the minimum steps using simple arithmetic operations from math.
This approach is concise, efficient, and commonly expected in interviews. It reduces the problem to a simple observation about diagonal movement on a grid.
Recommended for interviews: Interviewers expect the Chebyshev distance solution. The step-wise reasoning shows you understand the movement rules, but recognizing that the answer simplifies to max(|dx|, |dy|) demonstrates strong pattern recognition and knowledge of grid geometry. Both approaches run in O(n) time with constant space, but the mathematical formulation is cleaner and easier to implement under pressure.
This approach centers on calculating the time taken to move from one point to another based solely on the maximum of the differences between x and y coordinates. This works because moving diagonally allows us to cover one unit in both x and y directions simultaneously. Therefore, the time taken to move from one point to another is always determined by the greater of the horizontal or vertical distances needed to cover.
The C implementation iterates over the list of points, computes the differences in x and y coordinates between consecutive points, and adds the maximum of those differences to total time. It uses the built-in abs function to ensure it is working with positive differences.
Time Complexity: O(n), where n is the number of points. We process each pair of points once.
Space Complexity: O(1), as we use a constant amount of extra space.
This approach involves calculating the total distance for each x and y direction separately, but also accounting for the diagonal moves that can reduce total movement time. Here, the diagonal path is favored when both x and y movements can be made simultaneously, which is reflected in the use of the maximum function across the differences.
The C solution involves computing the minimum time based on adjusting x and y coordinates according to maximum differences while iterating through each pair of points.
Time Complexity: O(n), where n is the number of points. We process each pair once.
Space Complexity: O(1), as we are using a constant amount of space.
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.
If d_x \ge d_y, we move diagonally for d_y steps, then move horizontally for d_x - d_y steps; if d_x < d_y, we move diagonally for d_x steps, then move vertically for d_y - d_x steps. Therefore, the shortest distance between two points is max(d_x, d_y).
We can iterate through all pairs of points, calculate the shortest distance between each pair, and sum them up.
The time complexity is O(n), where n is the number of points. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Calculate Maximum of X and Y Differences | Time Complexity: O(n), where n is the number of points. We process each pair of points once. |
| Calculate Sum of Step-wise Distances | Time Complexity: O(n), where n is the number of points. We process each pair once. |
| Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sum of Step-wise Distances (Simulation) | O(n) | O(1) | Useful for understanding movement rules and reasoning about diagonal vs straight steps |
| Maximum of X and Y Differences (Chebyshev Distance) | O(n) | O(1) | Best general solution. Clean mathematical observation with minimal code |
Minimum Time Visiting All Points | LeetCode 1266 | C++, Java, Python • Knowledge Center • 11,125 views views
Watch 9 more video solutions →Practice Minimum Time Visiting All Points with our built-in code editor and test cases.
Practice on FleetCode