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] <= 1000In #1266 Minimum Time Visiting All Points, you are given a sequence of coordinates that must be visited in order. The key observation is that in one second you can move horizontally, vertically, or diagonally. Because diagonal movement changes both the x and y coordinates simultaneously, it allows you to reduce the distance in both directions at the same time.
For each pair of consecutive points, analyze the difference between their x and y coordinates. The optimal strategy is to take as many diagonal steps as possible, then finish with horizontal or vertical moves if needed. This leads to a simple geometric insight where the required time depends on the larger of the horizontal or vertical differences.
By iterating through the list of points and accumulating the required time between each pair, you can compute the total travel time efficiently. This approach runs in O(n) time and requires O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Iterate through consecutive points using geometric distance insight | O(n) | O(1) |
stoney codes
Use these hints if you're stuck. Try solving on your own first.
To walk from point A to point B there will be an optimal strategy to walk ?
Advance in diagonal as possible then after that go in straight line.
Repeat the process until visiting all the points.
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.
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.
1function minTimeToVisitAllPoints(points) {
2 let totalTime = 0;
3 for (let i = 0; i < points.length - 1; i++
The JavaScript solution follows similar logic to other languages, using Math.abs for absolute differences and Math.max for selecting the larger of the two, iterating through each point pair to derive a final time estimate.
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.
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.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
This problem represents the type of geometry and observation-based questions often asked in coding interviews. While it is categorized as easy, it tests a candidate’s ability to recognize movement patterns and optimize calculations.
Diagonal moves reduce both x and y distances in a single step. After using all possible diagonal moves, any remaining distance must be covered horizontally or vertically. Therefore, the total time equals the maximum of the horizontal and vertical differences.
Only a simple array traversal is required. The input is already provided as an array of coordinates, and the solution simply iterates through consecutive pairs to accumulate the required time.
The optimal approach uses a geometric observation. Since diagonal movement is allowed, you can reduce both x and y differences simultaneously. The time needed between two points is determined by the larger absolute difference between their x and y coordinates.
This Python function calculates the minimum visit time based on maximum spatial parity inclusion.