Minimum Time Visiting All Points

Easy
982.

Minimum Time Visiting All Points

Minimum Time Visiting All Points is an easy coding problem on arrays, math and geometry, asked in Amazon, Google and Wipro interviews.

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 == n
  • 1 <= n <= 100
  • points[i].length == 2
  • -1000 <= points[i][0], points[i][1] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} points
 * @return {number}
 */
var minTimeToVisitAllPoints = function(points) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 == n
  • 1 <= n <= 100
  • points[i].length == 2
  • -1000 <= points[i][0], points[i][1] <= 1000

Hints for Minimum Time Visiting All Points

  1. Hint 1

    A diagonal move changes both coordinates at once, so it costs the same as a single step.

  2. Hint 2

    Travelling between two points, the diagonal moves cover the smaller of the two gaps.

  3. 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

  1. For each consecutive pair, take dx = |x2 - x1| and dy = |y2 - y1|.
  2. 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 total

Java

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