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] <= 1000This 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
70 Leetcode problems in 5+ hours (every data structure) (full tutorial) • stoney codes • 750,478 views views
Watch 9 more video solutions →Practice Minimum Time Visiting All Points with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor