Minimum Time Visiting All Points
EasyPrompt
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 secondsExample 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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach simulates the movement from one point to the next, one second at a time. For each pair of consecutive points, we start at the first point and iteratively move towards the second point, incrementing a time counter with each move. The optimal move at each step is chosen greedily: a diagonal move if possible, otherwise a horizontal or vertical move.
Algorithm
- Initialize
totalTime = 0. - Iterate through the
pointsarray fromi = 0topoints.length - 2. - For each pair of consecutive points,
currentPoint = points[i]andnextPoint = points[i+1], start a simulation. - Let a temporary point
(currentX, currentY)be atcurrentPoint's coordinates. - Start an inner loop that continues as long as
(currentX, currentY)is not atnextPoint's coordinates. - Inside the inner loop, increment
totalTimeby 1 for each second of movement. - Move
(currentX, currentY)one step closer tonextPoint. If both x and y coordinates need to change, move diagonally. Otherwise, move horizontally or vertically. - Repeat until all segments between consecutive points are traversed.
- Return
totalTime.
Walkthrough
This method directly translates the problem's movement rules into a step-by-step simulation. We calculate the total time by adding up the time taken to travel between each consecutive pair of points. To find the time between two points, say start and end, we simulate the movement from start. In each second (i.e., each iteration), we move one unit in a direction that brings us closer to end. Since a diagonal move is most efficient (covering both horizontal and vertical distance in one second), we prioritize it. If we need to move in both x and y directions to reach the target, we make a diagonal move. If we only need to move along one axis, we make a horizontal or vertical move. We continue this process, incrementing a time counter at each step, until we reach the end point. The final answer is the sum of times for all such segments.
class Solution { public int minTimeToVisitAllPoints(int[][] points) { int totalTime = 0; for (int i = 0; i < points.length - 1; i++) { int currentX = points[i][0]; int currentY = points[i][1]; int targetX = points[i+1][0]; int targetY = points[i+1][1]; // Simulate the movement from current point to target point while (currentX != targetX || currentY != targetY) { // Move diagonally if possible if (currentX != targetX && currentY != targetY) { if (currentX < targetX) { currentX++; } else { currentX--; } if (currentY < targetY) { currentY++; } else { currentY--; } } else if (currentX != targetX) { // Move horizontally if (currentX < targetX) { currentX++; } else { currentX--; } } else { // Move vertically if (currentY < targetY) { currentY++; } else { currentY--; } } totalTime++; } } return totalTime; }}Complexity
Time
O(L), where L is the total number of unit moves (the final answer). In the worst case, this can be O(N * D), where N is the number of points and D is the maximum coordinate difference between any two consecutive points. This is inefficient.
Space
O(1) - We only use a few variables to store the current position and total time, regardless of the input size.
Trade-offs
Pros
Conceptually straightforward as it directly models the physical movement described in the problem.
Cons
Highly inefficient compared to the mathematical approach. The runtime depends on the magnitude of the coordinates, not just the number of points.
The implementation is more complex and verbose than necessary.
Solutions
Solution
class Solution { public int minTimeToVisitAllPoints ( int [][] points ) { int ans = 0 ; for ( int i = 1 ; i < points . length ; ++ i ) { int dx = Math . abs ( points [ i ][ 0 ] - points [ i - 1 ][ 0 ]); int dy = Math . abs ( points [ i ][ 1 ] - points [ i - 1 ][ 1 ]); ans += Math . max ( dx , dy ); } return ans ; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.