Minimum Time Visiting All Points

Easy

#1181Time: 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.1 company

Patterns

Math Geometry

Data structures

Array

Companies

Media.net

Prompt

On a 2D plane, there are n points with integer coordinates points[i] = [x_i, y_i]. 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 1 second, 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 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 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 == n
1 <= n <= 100
points[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 points array from i = 0 to points.length - 2.
For each pair of consecutive points, currentPoint = points[i] and nextPoint = points[i+1], start a simulation.
Let a temporary point (currentX, currentY) be at currentPoint's coordinates.
Start an inner loop that continues as long as (currentX, currentY) is not at nextPoint's coordinates.
Inside the inner loop, increment totalTime by 1 for each second of movement.
Move (currentX, currentY) one step closer to nextPoint. 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.

1class Solution {2    public int minTimeToVisitAllPoints(int[][] points) {3        int totalTime = 0;4        for (int i = 0; i < points.length - 1; i++) {5            int currentX = points[i][0];6            int currentY = points[i][1];7            int targetX = points[i+1][0];8            int targetY = points[i+1][1];9 10            // Simulate the movement from current point to target point11            while (currentX != targetX || currentY != targetY) {12                // Move diagonally if possible13                if (currentX != targetX && currentY != targetY) {14                    if (currentX < targetX) {15                        currentX++;16                    } else {17                        currentX--;18                    }19                    if (currentY < targetY) {20                        currentY++;21                    } else {22                        currentY--;23                    }24                } else if (currentX != targetX) { // Move horizontally25                    if (currentX < targetX) {26                        currentX++;27                    } else {28                        currentX--;29                    }30                } else { // Move vertically31                    if (currentY < targetY) {32                        currentY++;33                    } else {34                        currentY--;35                    }36                }37                totalTime++;38            }39        }40        return totalTime;41    }42}

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.

This approach leverages a key insight about the movement rules. A diagonal move covers one unit horizontally and one unit vertically in a single second, which is always at least as good as making separate horizontal and vertical moves. The minimum time to travel between two points (x1, y1) and (x2, y2) is therefore determined by the larger of the absolute differences in their coordinates, i.e., max(|x2 - x1|, |y2 - y1|). This is also known as the Chebyshev distance. The total time is simply the sum of these distances for all consecutive pairs of points.

Algorithm

Initialize totalTime = 0.
Iterate through the points array from the first point to the second-to-last, i.e., from i = 0 to n-2.
In each iteration, consider the current point p1 = points[i] and the next point p2 = points[i+1].
Calculate the absolute difference in the x-coordinates: dx = |p2[0] - p1[0]|.
Calculate the absolute difference in the y-coordinates: dy = |p2[1] - p1[1]|.
The minimum time to travel between p1 and p2 is the maximum of these two differences: time_for_segment = max(dx, dy).
Add this time to the totalTime.
After the loop completes, return totalTime.

Walkthrough

The core idea is to find a direct formula for the time taken to travel between any two points. Let the start point be (x1, y1) and the end point be (x2, y2). The horizontal distance to cover is dx = |x2 - x1| and the vertical distance is dy = |y2 - y1|.

Since a diagonal move takes 1 second and covers 1 unit in both x and y directions, we should maximize diagonal moves. We can make min(dx, dy) diagonal moves. This takes min(dx, dy) seconds.

After these diagonal moves, we have covered min(dx, dy) of the distance in both axes. The remaining distance is purely horizontal or vertical, equal to dx - min(dx, dy) and dy - min(dx, dy). One of these will be zero. The other will be |dx - dy|. This remaining distance requires |dx - dy| straight moves, taking |dx - dy| seconds.

The total time is the sum: min(dx, dy) + |dx - dy|. A useful mathematical identity is that for any non-negative a and b, min(a, b) + |a - b| = max(a, b). Therefore, the time to travel between two points is simply max(dx, dy).

The algorithm iterates through consecutive points, calculates this maximum difference for each pair, and sums them up to get the total minimum time.

1class Solution {2    public int minTimeToVisitAllPoints(int[][] points) {3        int totalTime = 0;4        for (int i = 0; i < points.length - 1; i++) {5            int dx = Math.abs(points[i+1][0] - points[i][0]);6            int dy = Math.abs(points[i+1][1] - points[i][1]);7            totalTime += Math.max(dx, dy);8        }9        return totalTime;10    }11}

Complexity

Time

O(N), where N is the number of points. We iterate through the array of points once.

Space

O(1) - Constant extra space is used, as we only need a few variables to store the distances and the total time.

Trade-offs

Pros

Extremely efficient with a linear time complexity.
Simple, concise, and elegant implementation.
Calculates the result directly without any slow, step-by-step simulation.

Cons

Requires the mathematical insight that the minimum time is the Chebyshev distance, which might not be immediately obvious to everyone.

Solutions

Solution

1class 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 ; } }

1class Solution : def minTimeToVisitAllPoints ( self , points : List [ List [ int ]]) -> int : return sum ( max ( abs ( p1 [ 0 ] - p2 [ 0 ]), abs ( p1 [ 1 ] - p2 [ 1 ])) for p1 , p2 in pairwise ( points ) )

1class Solution { public: int minTimeToVisitAllPoints ( vector < vector < int >>& points ) { int ans = 0 ; for ( int i = 1 ; i < points . size (); ++ i ) { int dx = abs ( points [ i ][ 0 ] - points [ i - 1 ][ 0 ]); int dy = abs ( points [ i ][ 1 ] - points [ i - 1 ][ 1 ]); ans += 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.

← Previous

Previous problem

Next problem