Problem Statement in English

You’re given an array points where points[i] = [xi, yi] represents a point on the X-Y plane.

You start at the first point points[0] and you want to visit all the points in order. You can move according to these rules:

  • In one second, you can either:
    • Move vertically by one unit.
    • Move horizontally by one unit.
    • Move diagonally (which is defined as moving one unit vertically and one unit horizontally in one second).
  • You have to visit the points in the order they appear in the points array.

Return the minimum time in seconds to visit all the points.

Approach

You need to use a little visualization to understand the movement rules.

The key observation is that when moving from one point to another, you can take advantage of diagonal moves to minimize the total time.

The next question is probably, how do I figure out when to move diagonally, and how many diagonal moves should I make?

If you think about it, you can always just move horizontally and vertically. Further, moving diagonally is simply the combination an equal number of horizontal and vertical moves.

So let’s say you make $5$ left and $8$ down moves. This means that you can make $min(5, 8) = 5$ diagonal moves, and then you will have to make the remaining $3$ down moves. So net net, you’ve just made $5+ 3 = 8$ moves.

So all we do is pick each consecutive pair of points, and calculate the number of horizontal and vertical moves needed. The answer for that pair of points is simply the sum of diagonal moves (the minimum of the number of vertical and horizontal moves) and the remaining moves (remove the common value from both horizontal and vertical moves).

Solution in Python


class Solution:
    def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
        res = 0

        for i in range(1, len(points)):
            x1, y1 = points[i - 1]
            x2, y2 = points[i]

            horizontal = abs(y2 - y1)
            vertical = abs(x2 - x1)

            common = min(vertical, horizontal)

            vertical -= common
            horizontal -= common

            res += vertical
            res += horizontal
            res += common

        return res

Complexity

  • Time: $O(n)$
    Since we just traverse the list of points once.

  • Space: $O(1)$
    Since we just use a few extra variables.

And we are done.