Skip to main content
Talentd

Minimum Time Visiting All Points - Solution & Explanation

EasyArrayMathGeometry17 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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:

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

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

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

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
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 the number of points. We process each pair once.
Space Complexity: O(1), as we are using a constant amount of space.

Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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

Video Solution

Minimum Time Visiting All Points | LeetCode 1266 | C++, Java, Python • Knowledge Center • 11,242 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Time Visiting All Points with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays