algoadvance

Given an array of points where points[i] = [xi, yi] represents a point on the 2D plane, return the minimum time in seconds to visit all the points in the order given by points.

You can move one unit distance in either the x-direction, y-direction, or diagonally (in both x and y direction).

Example

  1. Input: points = [[1,1],[3,4],[-1,0]] Output: 7 Explanation:
    • From (1,1) to (3,4), we can move 2 units diagonally to (3,3) and 1 unit to (3,4). Total = 3.
    • From (3,4) to (-1,0) we can move 4 units left to (-1,4) and 4 units down to (-1,0). Total = 4.
    • Therefore total time = 3 + 4 = 7.
  2. Input: points = [[3,2],[-2,2]] Output: 5 Explanation:
    • From (3,2) to (-2,2), we need to move 5 units left.

Constraints:

Clarifying Questions

  1. Q: Can we assume that the points are distinct? A: Yes, you can assume that each point is unique.
  2. Q: Can the points array be empty? A: No, points.length >= 1 as per the constraints.

Strategy

  1. Calculate the distance to travel between two consecutive points.
  2. The distance is determined by the max of the absolute difference of x-coordinates and y-coordinates because you can move diagonally.
    • For example, to move from (xi, yi) to (xf, yf), the minimum time would be max(abs(xf - xi), abs(yf - yi)).

Code

def minTimeToVisitAllPoints(points):
    total_time = 0
    
    for i in range(1, len(points)):
        x0, y0 = points[i - 1]
        x1, y1 = points[i]
        
        time_to_next_point = max(abs(x1 - x0), abs(y1 - y0))
        total_time += time_to_next_point
    
    return total_time

# Test cases
print(minTimeToVisitAllPoints([[1, 1], [3, 4], [-1, 0]]))  # Output: 7
print(minTimeToVisitAllPoints([[3, 2], [-2, 2]]))  # Output: 5

Time Complexity

The time complexity for this solution is O(n), where n is the number of points in the input list. This is because we iterate through the points exactly once.

Space Complexity

The space complexity is O(1) since we are using a fixed amount of extra space regardless of the input size.

Try our interview co-pilot at AlgoAdvance.com