1266. Minimum Time Visiting All Points Solution

Q: Is Minimum Time Visiting All Points easy or hard?

Minimum Time Visiting All Points is classified as an Easy problem with a high acceptance rate around 85%. The main challenge is recognizing that diagonal moves allow both coordinates to change at once, which leads to the Chebyshev distance formula.

Q: Minimum Time Visiting All Points Python/Java solution

In Python or Java, loop through the points and compute max(abs(x2 - x1), abs(y2 - y1)) for each adjacent pair. Add the result to a running total and return it. This produces an O(n) time and O(1) space implementation.

Q: How to solve Minimum Time Visiting All Points in O(n)?

Iterate through the array of points and process each consecutive pair. For points (x1, y1) and (x2, y2), compute dx = |x2 − x1| and dy = |y2 − y1|. The minimum time to move between them equals max(dx, dy). Add this value to a running total for all pairs.

Q: What is the best approach for Minimum Time Visiting All Points?

The best approach uses Chebyshev distance. For each pair of consecutive points, compute max(|x2 − x1|, |y2 − y1|) and sum the values. This works because diagonal moves reduce both coordinates simultaneously. The algorithm runs in O(n) time with O(1) extra space.

Q: Is Minimum Time Visiting All Points asked at Google/Amazon/Meta?

Grid movement and distance problems frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact question may vary, the underlying concept of Chebyshev distance and coordinate differences is a common interview pattern.

Q: What data structure is used in Minimum Time Visiting All Points?

The problem primarily uses arrays to store the list of coordinates. The logic relies on simple arithmetic and geometry rather than advanced data structures. Each step processes consecutive points using constant extra space.

Q: What is the time complexity of Minimum Time Visiting All Points?

The optimal solution runs in O(n) time where n is the number of points. You only iterate once through the list and compute coordinate differences for each consecutive pair. Space complexity is O(1) since only a few integer variables are used.

The problem

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

Approach overview

Problem Overview: You are given an ordered list of 2D points. Starting at the first point, you must visit every next point in sequence. In one second you can move horizontally, vertically, or diagonally. The task is to compute the minimum time required to travel through all points.

The key observation is that a diagonal move changes both x and y simultaneously. This means you should take as many diagonal steps as possible before finishing with horizontal or vertical moves.

Approach 1: Calculate Sum of Step-wise Distances (Simulation) (Time: O(n), Space: O(1))

Process each consecutive pair of points and simulate movement step by step. At each step, move diagonally while both coordinates differ. Once either the x or y coordinate matches the target, continue moving horizontally or vertically until you reach the point. For a pair of points (x1, y1) and (x2, y2), the number of diagonal steps equals min(|x2-x1|, |y2-y1|). The remaining difference is covered with straight moves.

This method reflects the physical movement rules and makes the reasoning easy to follow. You iterate through the array of points, calculate coordinate differences, and accumulate the required steps. Even though the logic mimics movement, the total steps simplify mathematically.

Approach 2: Calculate Maximum of X and Y Differences (Chebyshev Distance) (Time: O(n), Space: O(1))

The optimal insight comes from geometry. When diagonal movement is allowed, the shortest path between two grid points equals the Chebyshev distance. For points (x1, y1) and (x2, y2), the minimum number of seconds required is max(|x2 - x1|, |y2 - y1|). Diagonal moves reduce both coordinate differences simultaneously, so the larger difference determines the total time.

Iterate once through the points and compute this value for each consecutive pair. Add the result to a running total. This avoids simulating movement and directly computes the minimum steps using simple arithmetic operations from math.

This approach is concise, efficient, and commonly expected in interviews. It reduces the problem to a simple observation about diagonal movement on a grid.

Recommended for interviews: Interviewers expect the Chebyshev distance solution. The step-wise reasoning shows you understand the movement rules, but recognizing that the answer simplifies to max(|dx|, |dy|) demonstrates strong pattern recognition and knowledge of grid geometry. Both approaches run in O(n) time with constant space, but the mathematical formulation is cleaner and easier to implement under pressure.

Approach 1: Calculate Maximum of X and Y Differences

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.

Python

def minTimeToVisitAllPoints(points):
    total_time = 0
    for i in range(len(points) - 1):
        x_diff = abs(points[i+1][0] - points[i][0])
        y_diff = abs(points[i+1][1] - points[i][1])
        total_time += max(x_diff, y_diff)
    return total_time

points = [[1, 1], [3, 4], [-1, 0]]
print(minTimeToVisitAllPoints(points))

Java

public class MinimumTime {
    public static int minTimeToVisitAllPoints(int[][] points) {
        int totalTime = 0;
        for (int i = 0; i < points.length - 1; i++) {
            int xDiff = Math.abs(points[i + 1][0] - points[i][0]);
            int yDiff = Math.abs(points[i + 1][1] - points[i][1]);
            totalTime += Math.max(xDiff, yDiff);
        }
        return totalTime;
    }

    public static void main(String[] args) {
        int[][] points = {{1, 1}, {3, 4}, {-1, 0}};
        System.out.println(minTimeToVisitAllPoints(points));
    }
}

C++

#include <vector>
#include <cstdlib>
#include <algorithm>
#include <iostream>

using namespace std;

int minTimeToVisitAllPoints(vector<vector<int>>& points) {
    int totalTime = 0;
    for (size_t i = 0; i < points.size() - 1; ++i) {
        int xDiff = abs(points[i+1][0] - points[i][0]);
        int yDiff = abs(points[i+1][1] - points[i][1]);
        totalTime += max(xDiff, yDiff);
    }
    return totalTime;
}

int main() {
    vector<vector<int>> points = {{1, 1}, {3, 4}, {-1, 0}};
    cout << minTimeToVisitAllPoints(points) << endl;
    return 0;
}

JavaScript

function minTimeToVisitAllPoints(points) {
    let totalTime = 0;
    for (let i = 0; i < points.length - 1; i++) {
        const xDiff = Math.abs(points[i+1][0] - points[i][0]);
        const yDiff = Math.abs(points[i+1][1] - points[i][1]);
        totalTime += Math.max(xDiff, yDiff);
    }
    return totalTime;
}

const points = [[1, 1], [3, 4], [-1, 0]];
console.log(minTimeToVisitAllPoints(points));

#include <stdio.h>
#include <stdlib.h>

int minTimeToVisitAllPoints(int** points, int pointsSize, int* pointsColSize) {
    int totalTime = 0;
    for (int i = 0; i < pointsSize - 1; ++i) {
        int xDiff = abs(points[i + 1][0] - points[i][0]);
        int yDiff = abs(points[i + 1][1] - points[i][1]);
        totalTime += xDiff > yDiff ? xDiff : yDiff;
    }
    return totalTime;
}

int main() {
    int pointsSize = 3;
    int pointsColSize[] = {2, 2, 2};
    int* points[] = {(int[]){1, 1}, (int[]){3, 4}, (int[]){-1, 0}};
    printf("%d\n", minTimeToVisitAllPoints(points, pointsSize, pointsColSize));
    return 0;
}

using System;

class MinimumTime {
    public static int MinTimeToVisitAllPoints(int[][] points) {
        int totalTime = 0;
        for (int i = 0; i < points.Length - 1; i++) {
            int xDiff = Math.Abs(points[i + 1][0] - points[i][0]);
            int yDiff = Math.Abs(points[i + 1][1] - points[i][1]);
            totalTime += Math.Max(xDiff, yDiff);
        }
        return totalTime;
    }

    static void Main() {
        int[][] points = new int[][] {
            new int[] {1, 1},
            new int[] {3, 4},
            new int[] {-1, 0}
        };
        Console.WriteLine(MinTimeToVisitAllPoints(points));
    }
}

This Python solution traverses the points, computing absolute differences in x and y coordinates for consecutive points. The maximum of these is summed into a total that gives the minimum time required for traversal.

Complexity

Time Complexity: O(n), where n is the number of points.
Space Complexity: O(1), as we use a constant amount of extra space.

Try this approach in the editor

Approach 2: Calculate Sum of Step-wise Distances

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.

Python

def minTimeToVisitAllPoints(points):
    total_time = 0
    for i in range(len(points) - 1):
        x_diff = abs(points[i+1][0] - points[i][0])
        y_diff = abs(points[i+1][1] - points[i][1])
        total_time += max(x_diff, y_diff)
    return total_time

points = [[3, 2], [-2, 2]]
print(minTimeToVisitAllPoints(points))

Java

public class MinimumTime {
    public static int minTimeToVisitAllPoints(int[][] points) {
        int totalTime = 0;
        for (int i = 0; i < points.length - 1; i++) {
            int xDiff = Math.abs(points[i + 1][0] - points[i][0]);
            int yDiff = Math.abs(points[i + 1][1] - points[i][1]);
            totalTime += Math.max(xDiff, yDiff);
        }
        return totalTime;
    }

    public static void main(String[] args) {
        int[][] points = {{3, 2}, {-2, 2}};
        System.out.println(minTimeToVisitAllPoints(points));
    }
}

C++

#include <vector>
#include <cstdlib>
#include <algorithm>
#include <iostream>

using namespace std;

int minTimeToVisitAllPoints(vector<vector<int>>& points) {
    int totalTime = 0;
    for (size_t i = 0; i < points.size() - 1; ++i) {
        int xDiff = abs(points[i + 1][0] - points[i][0]);
        int yDiff = abs(points[i + 1][1] - points[i][1]);
        totalTime += max(xDiff, yDiff);
    }
    return totalTime;
}

int main() {
    vector<vector<int>> points = {{3, 2}, {-2, 2}};
    cout << minTimeToVisitAllPoints(points) << endl;
    return 0;
}

JavaScript

function minTimeToVisitAllPoints(points) {
    let totalTime = 0;
    for (let i = 0; i < points.length - 1; i++) {
        const xDiff = Math.abs(points[i+1][0] - points[i][0]);
        const yDiff = Math.abs(points[i+1][1] - points[i][1]);
        totalTime += Math.max(xDiff, yDiff);
    }
    return totalTime;
}

const points = [[3, 2], [-2, 2]];
console.log(minTimeToVisitAllPoints(points));

#include <stdio.h>
#include <stdlib.h>

int minTimeToVisitAllPoints(int** points, int pointsSize, int* pointsColSize) {
    int totalTime = 0;
    for (int i = 0; i < pointsSize - 1; ++i) {
        int xDiff = abs(points[i + 1][0] - points[i][0]);
        int yDiff = abs(points[i + 1][1] - points[i][1]);
        totalTime += xDiff > yDiff ? xDiff : yDiff;
    }
    return totalTime;
}

int main() {
    int pointsSize = 2;
    int pointsColSize[] = {2, 2};
    int* points[] = {(int[]){3, 2}, (int[]){-2, 2}};
    printf("%d\n", minTimeToVisitAllPoints(points, pointsSize, pointsColSize));
    return 0;
}

using System;

class MinimumTime {
    public static int MinTimeToVisitAllPoints(int[][] points) {
        int totalTime = 0;
        for (int i = 0; i < points.Length - 1; i++) {
            int xDiff = Math.Abs(points[i + 1][0] - points[i][0]);
            int yDiff = Math.Abs(points[i + 1][1] - points[i][1]);
            totalTime += Math.Max(xDiff, yDiff);
        }
        return totalTime;
    }

    static void Main() {
        int[][] points = new int[][] {
            new int[] {3, 2},
            new int[] {-2, 2}
        };
        Console.WriteLine(MinTimeToVisitAllPoints(points));
    }
}

This Python function calculates the minimum visit time based on maximum spatial parity inclusion.

Complexity

Time Complexity: O(n), where n is number of points.
Space Complexity: O(1), uses constant space.

Try this approach in the editor

Approach 3: Simulation

For two points p_1=(x_1, y_1) and p_2=(x_2, y_2), the distances moved in the horizontal and vertical directions are d_x = |x_1 - x_2| and d_y = |y_1 - y_2| respectively.

If d_x \ge d_y, we move diagonally for d_y steps, then move horizontally for d_x - d_y steps; if d_x < d_y, we move diagonally for d_x steps, then move vertically for d_y - d_x steps. Therefore, the shortest distance between two points is max(d_x, d_y).

We can iterate through all pairs of points, calculate the shortest distance between each pair, and sum them up.

The time complexity is O(n), where n is the number of points. The space complexity is O(1).

TypeScript

function minTimeToVisitAllPoints(points: number[][]): number {
    let ans = 0;
    for (let i = 1; i < points.length; i++) {
        const dx = Math.abs(points[i][0] - points[i - 1][0]);
        const dy = Math.abs(points[i][1] - points[i - 1][1]);
        ans += Math.max(dx, dy);
    }
    return ans;
}

func minTimeToVisitAllPoints(points [][]int) (ans int) {
	for i, p := range points[1:] {
		dx := abs(p[0] - points[i][0])
		dy := abs(p[1] - points[i][1])
		ans += max(dx, dy)
	}
	return
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

Rust

impl Solution {
    pub fn min_time_to_visit_all_points(points: Vec<Vec<i32>>) -> i32 {
        let mut ans = 0;
        for i in 1..points.len() {
            let dx = (points[i][0] - points[i - 1][0]).abs();
            let dy = (points[i][1] - points[i - 1][1]).abs();
            ans += dx.max(dy);
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Calculate Maximum of X and Y Differences	Time Complexity: O(n), where n is the number of points. Space Complexity: O(1), as we use a constant amount of extra space.
Calculate Sum of Step-wise Distances	Time Complexity: O(n), where n is number of points. Space Complexity: O(1), uses constant space.
Simulation	–

Complexity analysis

Approach	Time	Space	When to Use
Sum of Step-wise Distances (Simulation)	O(n)	O(1)	Useful for understanding movement rules and reasoning about diagonal vs straight steps
Maximum of X and Y Differences (Chebyshev Distance)	O(n)	O(1)	Best general solution. Clean mathematical observation with minimal code

Frequently asked questions

Is Minimum Time Visiting All Points easy or hard?

Minimum Time Visiting All Points is classified as an Easy problem with a high acceptance rate around 85%. The main challenge is recognizing that diagonal moves allow both coordinates to change at once, which leads to the Chebyshev distance formula.

Minimum Time Visiting All Points Python/Java solution

In Python or Java, loop through the points and compute max(abs(x2 - x1), abs(y2 - y1)) for each adjacent pair. Add the result to a running total and return it. This produces an O(n) time and O(1) space implementation.

How to solve Minimum Time Visiting All Points in O(n)?

Iterate through the array of points and process each consecutive pair. For points (x1, y1) and (x2, y2), compute dx = |x2 − x1| and dy = |y2 − y1|. The minimum time to move between them equals max(dx, dy). Add this value to a running total for all pairs.

What is the best approach for Minimum Time Visiting All Points?

The best approach uses Chebyshev distance. For each pair of consecutive points, compute max(|x2 − x1|, |y2 − y1|) and sum the values. This works because diagonal moves reduce both coordinates simultaneously. The algorithm runs in O(n) time with O(1) extra space.

Is Minimum Time Visiting All Points asked at Google/Amazon/Meta?

Grid movement and distance problems frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact question may vary, the underlying concept of Chebyshev distance and coordinate differences is a common interview pattern.

What data structure is used in Minimum Time Visiting All Points?

The problem primarily uses arrays to store the list of coordinates. The logic relies on simple arithmetic and geometry rather than advanced data structures. Each step processes consecutive points using constant extra space.

What is the time complexity of Minimum Time Visiting All Points?

The optimal solution runs in O(n) time where n is the number of points. You only iterate once through the list and compute coordinate differences for each consecutive pair. Space complexity is O(1) since only a few integer variables are used.

Minimum Time Visiting All Points solution and explanation

The problem

Approach overview

Approach 1: Calculate Maximum of X and Y Differences

Approach 2: Calculate Sum of Step-wise Distances

Approach 3: Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Time Visiting All Points solution and explanation

The problem

Approach overview

Approach 1: Calculate Maximum of X and Y Differences

Approach 2: Calculate Sum of Step-wise Distances

Approach 3: Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems