Minimum Time Visiting All Points — Problem & Solution
Minimum Time Visiting All Points solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Minimum Time Visiting All Points is an easy coding problem on arrays, math and geometry, asked in Amazon, Google and Wipro interviews.
- Difficulty: Easy
- Topics: Arrays, Math, Geometry
- Asked at: Amazon, Google, Wipro
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
On a plane you may move one unit vertically, one unit horizontally, or one unit diagonally — each move takes one second.
Visit the given points in the order they appear and return the minimum number of seconds.
Example 1
Input: points = [[1,1],[3,4],[-1,0]]
Output: 7
Explanation: Three seconds from `(1,1)` to `(3,4)`, then four more to `(-1,0)`.
Example 2
Input: points = [[3,2],[-2,2]]
Output: 5
Explanation: A straight horizontal run of five.
Example 3
Input: points = [[0,0],[0,0]]
Output: 0
Constraints
points.length == n1 <= n <= 100points[i].length == 2-1000 <= points[i][0], points[i][1] <= 1000
Hints for Minimum Time Visiting All Points
Hint 1
A diagonal move changes both coordinates at once, so it costs the same as a single step.
Hint 2
Travelling between two points, the diagonal moves cover the smaller of the two gaps.
Hint 3
That leaves the difference of the gaps to cover straight — which totals the larger gap.
How to solve Minimum Time Visiting All Points
Between consecutive points the time is the Chebyshev distance: max(|dx|, |dy|). Sum it over the consecutive pairs.
Approach
- For each consecutive pair, take
dx = |x2 - x1|anddy = |y2 - y1|. - Add
max(dx, dy)to the total.
Why it works
Move diagonally min(dx, dy) times to close the smaller gap, then straight for the remaining |dx - dy| steps — that is max(dx, dy) moves in total, and no faster route exists because each move changes either coordinate by at most 1. The points must be visited in order, so the pairs are independent and simply add.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Manhattan distance (
dx + dy) overcounts; diagonals are free extras. - The order is fixed — this is not a travelling-salesman question.
- Coordinates can be negative, so take absolute differences.
Reference solution
Python
from typing import List
def minTimeToVisitAllPoints(points: List[List[int]]) -> int:
total = 0
for i in range(1, len(points)):
dx = abs(points[i][0] - points[i - 1][0])
dy = abs(points[i][1] - points[i - 1][1])
total += max(dx, dy)
return totalJava
public static int minTimeToVisitAllPoints(int[][] points) {
int total = 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]);
total += Math.max(dx, dy);
}
return total;
}C++
int minTimeToVisitAllPoints(vector<vector<int>>& points) {
int total = 0;
for (size_t 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]);
total += max(dx, dy);
}
return total;
}JavaScript
var minTimeToVisitAllPoints = function(points) {
var total = 0;
for (var i = 1; i < points.length; i++) {
var dx = Math.abs(points[i][0] - points[i - 1][0]);
var dy = Math.abs(points[i][1] - points[i - 1][1]);
total += dx > dy ? dx : dy;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays