Problem Description

The goal of the problem is to find the minimum time it takes to visit all points. These points are given as n points with integer coordinates on a plane. You can move vertically, horizontally, or diagonally in one-second intervals.

The main challenge is that you have to visit the points in the same order as they appear in the array, which means that you can't just go to the closest point every time.

Example

Taking the first example from the problem description:

1. The points are [[1,1],[3,4],[-1,0]]
2. One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]
3. The total time is 7 seconds which is the output

Solution Approach

A good way to solve this problem is to look at each pair of points (e.g. points[i], points[i+1]) and calculate the minimum time it would take to get from one to the other. Once this is done for all pairs, all these times can be added together to get the total minimum time.

We will calculate the time between two points with the formula max(|x2 - x1|, |y2 - y1|). The reason for this is that we can move diagonally, which allows us to get from one point to another faster. Specifically, moving diagonally allows us to cover one unit of distance along both the x and y axes in a single step.

For example, if one point is at (3, 2) and the other is at (-2, 2), the time to get from the first point to the second would be max(|-2 - 3|, |2 - 2|) = max(5, 0) = 5.

Algorithm Steps

1. Take an initial time variable as zero.
2. Loop through the point list from the 2nd point (i=1)
3. For each point, calculate the time to reach from i-1 to current point i with formula: max(|xi - xi-1|, |yi - y|).
4. Keep adding the time to the initial time variable.
5. Return the total time.

Python Solution

1
2python
3class Solution:
4    def minTimeToVisitAllPoints(self, points):
5        ans = 0
6        for i in range(1, len(points)):
7            # calculating the time to reach each point from the previous one
8            ans += max(abs(points[i][0] - points[i - 1][0]),
9                     abs(points[i][1] - points[i - 1][1]))
10        return ans

Java Solution

1
2java
3class Solution {
4    public int minTimeToVisitAllPoints(int[][] points) {
5     int ans = 0;
6        for (int i = 1; i < points.length; ++i)
7            ans += Math.max(Math.abs(points[i][0] - points[i - 1][0]),
8                           Math.abs(points[i][1] - points[i - 1][1]));
9        return ans;
10    }
11}

Javascript Solution

1
2javascript
3class Solution {
4    minTimeToVisitAllPoints(points) {
5    let ans = 0;
6        for (let i = 1; i < points.length; ++i)
7            ans += Math.max(Math.abs(points[i][0] - points[i - 1][0]),
8                      Math.abs(points[i][1] - points[i - 1][1]));
9        return ans;
10    }
11};

C++ Solution

1
2cpp
3class Solution {
4 public:
5  int minTimeToVisitAllPoints(vector<vector<int>>& points) {
6    int ans = 0;
7    for (int i = 1; i < points.size(); ++i)
8      ans += max(abs(points[i][0] - points[i - 1][0]),
9                 abs(points[i][1] - points[i - 1][1]));
10    return ans;
11  }
12};

C# Solution

1
2csharp
3public class Solution {
4    public int MinTimeToVisitAllPoints(int[][] points) {
5        int ans = 0;
6        for (int i = 1; i < points.Length; ++i)
7            ans += Math.Max(Math.Abs(points[i][0] - points[i - 1][0]),
8                            Math.Abs(points[i][1] - points[i - 1][1]));
9        return ans;
10    }
11};

Explanation: All solutions first start by initializing a variable 'ans' to hold the sum of time to visit each point starting from second position. In the loop, the maximum difference in either x-coordinates or y-coordinates between current and previous point is calculated and added to 'ans'. This because moving diagonally minimizes the time it takes to reach the next point. At the end of the iterations 'ans' holds the total minimum time to visit all points.# Ruby Solution

1
2ruby
3def min_time_to_visit_all_points(points)
4    ans = 0
5    for i in 1...points.length
6        ans += [(points[i][0] - points[i - 1][0]).abs, (points[i][1] - points[i - 1][1]).abs].max
7    end
8    ans
9end

PHP Solution

1
2php
3function minTimeToVisitAllPoints($points) {
4    $ans = 0;
5    for ($i = 1; $i < count($points); ++$i)
6        $ans += max(abs($points[$i][0] - $points[$i - 1][0]),
7                    abs($points[$i][1] - $points[$i - 1][1]));
8    return $ans;
9}

Swift Solution

1
2swift
3func minTimeToVisitAllPoints(_ points: [[Int]]) -> Int {
4    var ans = 0
5    for i in 1..<points.count{
6        ans += max(abs(points[i][0] - points[i - 1][0]),
7                   abs(points[i][1] - points[i - 1][1]))
8    }
9    return ans
10}

Kotlin Solution

1
2kotlin
3fun minTimeToVisitAllPoints(points: Array<IntArray>): Int {
4    var ans = 0
5    for (i in 1 until points.size)
6        ans += maxOf(Math.abs(points[i][0] - points[i - 1][0]),
7                     Math.abs(points[i][1] - points[i - 1][1]))
8    return ans
9}

In all these solutions, the overall time complexity is O(n), where n is total number of points. This is because we are iterating over the list of points only once. The space complexity is O(1), as we are only using a constant amount of space to store our answer variable. These solutions are both efficient and practical, even for large inputs. If the input is sorted in a particular way, no optimization will change our time complexity. That's because we need to calculate the time for each point from its previous point which requires us to go through each point at least once, hence, a time complexity of O(n) is the best we can achieve for this problem.