Minimum Time Visiting All Points: Understanding

Question

I was trying to solve a question from leetcode - "Minimum Time Visiting All Points". Below is the description of the problem -

On a plane there are n points with integer coordinates points[i] = [xi, yi]. Your task is to find the minimum time in seconds to visit all points.

You can move according to the next rules:

In one second always you can either move vertically, horizontally by one unit or diagonally (it means to move one unit vertically and one unit horizontally in one second). You have to visit the points in the same order as they appear in the array.

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

By solving a few examples i was able to solve the question in this way -

ans += max(abs(points[i][1] - points[i - 1][1]), abs(points[i][0] - points[i - 1][0]))

by looping 'i' from 1 to points.size() but i am unable to understand this problem intuitively. Can someone please help me in internalizing this problem?

Answer 1

Since you can move diagonally, the number of moves is bound only by the longest dimension, either x or y. Think about it: If the next node is +10x and -5y away, it's going to take exactly 10 steps, because you can only move 1 x at a time and the difference in y is made up by diagonal moves during the process of overcoming the difference in x.

This detail is expressed clearly by your code:

if dy = abs(points[i][1] - points[i - 1][1])

and dx = abs(points[i][0] - points[i - 1][0])

you can find precisely how many steps it will take by taking whichever of dx and dy is larger, because the smaller difference will be overcome by diagonal steps to get to the larger anyway. Hence, you have:

ans += max(dy, dx)

and this is guaranteed to always give you the correct number of steps for each pair of points. And as @flowit pointed out, the shortest path between each consecutive pair of points is guaranteed to be the shortest path for the entire set of points, hence you get the correct overall answer.