# Minimum Time Visiting All Points
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-time-visiting-all-points)
Canonical: https://scaleengineer.com/dsa/problems/minimum-time-visiting-all-points
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry)
**Data structures:** Array
**Companies:** [Media.net](https://scaleengineer.com/companies/media.net)
---
## Problem
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:**

![](https://assets.glich.co/dsa/minimum-time-visiting-all-points/image0.PNG) 

**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`

# Approaches
## Step-by-Step Simulation
This approach simulates the movement from one point to the next, one second at a time. For each pair of consecutive points, we start at the first point and iteratively move towards the second point, incrementing a time counter with each move. The optimal move at each step is chosen greedily: a diagonal move if possible, otherwise a horizontal or vertical move.
**Time:** O(L), where L is the total number of unit moves (the final answer). In the worst case, this can be O(N * D), where N is the number of points and D is the maximum coordinate difference between any two consecutive points. This is inefficient. · **Space:** O(1) - We only use a few variables to store the current position and total time, regardless of the input size.
**Pros:** Conceptually straightforward as it directly models the physical movement described in the problem.
**Cons:** Highly inefficient compared to the mathematical approach. The runtime depends on the magnitude of the coordinates, not just the number of points.; The implementation is more complex and verbose than necessary.
### Explanation
This method directly translates the problem's movement rules into a step-by-step simulation. We calculate the total time by adding up the time taken to travel between each consecutive pair of points. To find the time between two points, say `start` and `end`, we simulate the movement from `start`. In each second (i.e., each iteration), we move one unit in a direction that brings us closer to `end`. Since a diagonal move is most efficient (covering both horizontal and vertical distance in one second), we prioritize it. If we need to move in both x and y directions to reach the target, we make a diagonal move. If we only need to move along one axis, we make a horizontal or vertical move. We continue this process, incrementing a time counter at each step, until we reach the `end` point. The final answer is the sum of times for all such segments.

```java
class Solution {
    public int minTimeToVisitAllPoints(int[][] points) {
        int totalTime = 0;
        for (int i = 0; i < points.length - 1; i++) {
            int currentX = points[i][0];
            int currentY = points[i][1];
            int targetX = points[i+1][0];
            int targetY = points[i+1][1];

            // Simulate the movement from current point to target point
            while (currentX != targetX || currentY != targetY) {
                // Move diagonally if possible
                if (currentX != targetX && currentY != targetY) {
                    if (currentX < targetX) {
                        currentX++;
                    } else {
                        currentX--;
                    }
                    if (currentY < targetY) {
                        currentY++;
                    } else {
                        currentY--;
                    }
                } else if (currentX != targetX) { // Move horizontally
                    if (currentX < targetX) {
                        currentX++;
                    } else {
                        currentX--;
                    }
                } else { // Move vertically
                    if (currentY < targetY) {
                        currentY++;
                    } else {
                        currentY--;
                    }
                }
                totalTime++;
            }
        }
        return totalTime;
    }
}
```
### Algorithm
1. Initialize `totalTime = 0`.
2. Iterate through the `points` array from `i = 0` to `points.length - 2`.
3. For each pair of consecutive points, `currentPoint = points[i]` and `nextPoint = points[i+1]`, start a simulation.
4. Let a temporary point `(currentX, currentY)` be at `currentPoint`'s coordinates.
5. Start an inner loop that continues as long as `(currentX, currentY)` is not at `nextPoint`'s coordinates.
6. Inside the inner loop, increment `totalTime` by 1 for each second of movement.
7. Move `(currentX, currentY)` one step closer to `nextPoint`. If both x and y coordinates need to change, move diagonally. Otherwise, move horizontally or vertically.
8. Repeat until all segments between consecutive points are traversed.
9. Return `totalTime`.

## Optimal Mathematical Approach (Chebyshev Distance)
This approach leverages a key insight about the movement rules. A diagonal move covers one unit horizontally and one unit vertically in a single second, which is always at least as good as making separate horizontal and vertical moves. The minimum time to travel between two points `(x1, y1)` and `(x2, y2)` is therefore determined by the larger of the absolute differences in their coordinates, i.e., `max(|x2 - x1|, |y2 - y1|)`. This is also known as the Chebyshev distance. The total time is simply the sum of these distances for all consecutive pairs of points.
**Time:** O(N), where N is the number of points. We iterate through the array of points once. · **Space:** O(1) - Constant extra space is used, as we only need a few variables to store the distances and the total time.
**Pros:** Extremely efficient with a linear time complexity.; Simple, concise, and elegant implementation.; Calculates the result directly without any slow, step-by-step simulation.
**Cons:** Requires the mathematical insight that the minimum time is the Chebyshev distance, which might not be immediately obvious to everyone.
### Explanation
The core idea is to find a direct formula for the time taken to travel between any two points. Let the start point be `(x1, y1)` and the end point be `(x2, y2)`. The horizontal distance to cover is `dx = |x2 - x1|` and the vertical distance is `dy = |y2 - y1|`.

Since a diagonal move takes 1 second and covers 1 unit in both x and y directions, we should maximize diagonal moves. We can make `min(dx, dy)` diagonal moves. This takes `min(dx, dy)` seconds.

After these diagonal moves, we have covered `min(dx, dy)` of the distance in both axes. The remaining distance is purely horizontal or vertical, equal to `dx - min(dx, dy)` and `dy - min(dx, dy)`. One of these will be zero. The other will be `|dx - dy|`. This remaining distance requires `|dx - dy|` straight moves, taking `|dx - dy|` seconds.

The total time is the sum: `min(dx, dy) + |dx - dy|`. A useful mathematical identity is that for any non-negative `a` and `b`, `min(a, b) + |a - b| = max(a, b)`. Therefore, the time to travel between two points is simply `max(dx, dy)`.

The algorithm iterates through consecutive points, calculates this maximum difference for each pair, and sums them up to get the total minimum time.

```java
class Solution {
    public int minTimeToVisitAllPoints(int[][] points) {
        int totalTime = 0;
        for (int i = 0; i < points.length - 1; i++) {
            int dx = Math.abs(points[i+1][0] - points[i][0]);
            int dy = Math.abs(points[i+1][1] - points[i][1]);
            totalTime += Math.max(dx, dy);
        }
        return totalTime;
    }
}
```
### Algorithm
1. Initialize `totalTime = 0`.
2. Iterate through the `points` array from the first point to the second-to-last, i.e., from `i = 0` to `n-2`.
3. In each iteration, consider the current point `p1 = points[i]` and the next point `p2 = points[i+1]`.
4. Calculate the absolute difference in the x-coordinates: `dx = |p2[0] - p1[0]|`.
5. Calculate the absolute difference in the y-coordinates: `dy = |p2[1] - p1[1]|`.
6. The minimum time to travel between `p1` and `p2` is the maximum of these two differences: `time_for_segment = max(dx, dy)`.
7. Add this time to the `totalTime`.
8. After the loop completes, return `totalTime`.

# Solutions
### Java

```java
class Solution { public int minTimeToVisitAllPoints ( int [][] points ) { int ans = 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 ]); ans += Math . max ( dx , dy ); } return ans ; } }
```

### Python

```python
class Solution : def minTimeToVisitAllPoints ( self , points : List [ List [ int ]]) -> int : return sum ( max ( abs ( p1 [ 0 ] - p2 [ 0 ]), abs ( p1 [ 1 ] - p2 [ 1 ])) for p1 , p2 in pairwise ( points ) )
```

### CPP

```cpp
class Solution { public: int minTimeToVisitAllPoints ( vector < vector < int >>& points ) { int ans = 0 ; for ( int 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 ]); ans += max ( dx , dy ); } return ans ; } };
```