Minimum Time Visiting All Points - Video Solutions
Minimum Time Visiting All Points | LeetCode 1266 | C++, Java, Python
Minimum Time Visiting All Points - Video Solution
Watch 10 video solutions for Minimum Time Visiting All Points, a easy level problem involving Array, Math, Geometry. This walkthrough by Knowledge Center has 11,242 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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:
- In
1second, you can either:- move vertically by one unit,
- move horizontally by one unit, or
- move diagonally
sqrt(2)units (in other words, move one unit vertically then one unit horizontally in1second).
- 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 these do not count as visits.
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] <= 1000
Approach Overview
Problem 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.
Complexity Analysis
| 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 |