CODEWITHSUNDEEP
c++
J-T
J-T

Reputation: 43

Minimum Time Visiting All Points: Understanding

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?

Upvotes: 4

Views: 3043

Answers (6)

Abhinandan G
Abhinandan G

Reputation: 1

p=[[1, 1], [3, 4], [-1, 0]]
s=0
for i in range(len(p) - 1):
    l = max(abs(p[i][0] - p[i+1][0]), abs(p[i][1] - p[i+1][1]))
    s = s + l
print(s)

Upvotes: 0

Mazhar MIK
Mazhar MIK

Reputation: 1192

Just to add an extra thing as well in case anyone is looking for more :

    Key: The time to visit from point (x1, x2) and (y1, y2) is given by
         min(dx, dy) + abs(dx - dy);
         where, dx = abs(x2-x1) , dy = abs(y2-y1)

enter image description here

If you see the figure above: source : (1, 1)
Target : (3, 4)
dx = abs(x2-x1) = 2
dy = abs(y2-y1) = 3
1st Step and 2nd Step we moved diagonally.
The 3rd step that we took is actually equal to (dy-dx)
(Read the comment : Square of side = dx).
So, first we travel diagonally as far as we can and then we try to reach the target by moving vertically/horizontally.

Upvotes: 0

Vasantha Bhanu
Vasantha Bhanu

Reputation: 1

If someone is still confused there, essentially the core logic is

max_distance = max(abs(x2-x1), abs(y2-y1))

This max_distance number gives the number of seconds from point 1 = [x1, y1] to point 2 = [x2, y2].

Then, you repeat the same logic for point 2 and point 3 and so on.

Finally you add all the max_distances, which should give you the answer

Upvotes: -1

user2986249
user2986249

Reputation: 25

class Solution:
    def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
        path = 0
        for i in range(len(points) -1):
            path += max(abs(points[i][0] - points[i+1][0]), abs(points[i][1] - points[i+1][1])) 
        return path

Upvotes: 0

Chris94549
Chris94549

Reputation: 175

If anyone else is struggling with this, just draw the points out on paper and manually count the different ways to move between the points. You will immediately grasp that the shortest distance is the longest of the X or Y side, because moving diagonally is counted as 1, i.e. the same as an X or Y movement.

Upvotes: 1

Klaycon
Klaycon

Reputation: 11080

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.

Upvotes: 10

Related Questions