LeetCode Problem 1266

Difficulty: 🟢 Easy
Topics: Array, Math, Geometry

Solution

LeetCode 1266 - Minimum Time Visiting All Points

Problem Understanding

The problem gives a sequence of points on a 2D coordinate plane. Each point is represented as [x, y], where x and y are integer coordinates. Your task is to determine the minimum number of seconds required to visit every point in the exact order they appear in the input array.

Movement rules are extremely important here. In one second, you may:

• Move one unit horizontally
• Move one unit vertically
• Move one unit diagonally

A diagonal move changes both the x and y coordinates by one unit at the same time. For example, moving from (1,1) to (2,2) takes exactly one second because it is a diagonal move.

The key detail is that points must be visited in order. You cannot rearrange the points to optimize the route. However, you are allowed to pass through future points before officially visiting them later.

The input size is small, with at most 100 points, and coordinates range from -1000 to 1000. These constraints tell us that performance is not a major concern, but the problem still expects us to identify the mathematical shortcut that gives the minimum travel time directly.

A naive implementation could incorrectly assume that distance should be calculated using Euclidean distance or Manhattan distance. Neither is correct for this movement system. The diagonal movement changes the cost structure significantly.

Several edge cases are important:

• A single point requires zero movement, so the answer is 0.
• Points may already share the same x coordinate or same y coordinate, meaning only vertical or horizontal movement is needed.
• Coordinates may be negative.
• Consecutive points could even be identical, requiring zero time for that segment.

The problem guarantees valid input structure, so we do not need to handle malformed arrays.

Approaches

Brute Force Approach

The brute-force idea is to simulate movement one second at a time between every pair of consecutive points.

Suppose we are moving from (x1, y1) to (x2, y2). At every second, we attempt a diagonal move whenever both coordinates still differ. Once one coordinate matches the target, we continue moving horizontally or vertically until the destination is reached.

For example:

• From (1,1) to (4,3)
• Move diagonally to (2,2)
• Move diagonally to (3,3)
• Move horizontally to (4,3)

This simulation is correct because diagonal moves reduce both coordinate differences simultaneously, making them the most efficient moves whenever possible.

However, explicitly simulating every step is unnecessary. Although the constraints are small, the simulation approach performs extra work and obscures the mathematical insight behind the problem.

Optimal Approach

The key observation is that diagonal movement allows us to reduce both x and y differences at the same time.

For two points:

• Horizontal distance = abs(x2 - x1)
• Vertical distance = abs(y2 - y1)

We can perform diagonal moves until one coordinate becomes aligned. The number of diagonal moves possible is the smaller of the two differences.

After that, only straight moves remain.

This means the total minimum time is simply:

$$\max(|x2 - x1|, |y2 - y1|)$$

The larger difference determines the total time because diagonal moves reduce both coordinates simultaneously.

For example:

• From (1,1) to (4,3)
• dx = 3
• dy = 2
• Two diagonal moves reduce both
• One horizontal move remains
• Total time = max(3,2) = 3

So the algorithm becomes:

1. Iterate through consecutive pairs of points.
2. Compute dx and dy.
3. Add max(dx, dy) to the answer.

This produces the minimum travel time efficiently and directly.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(total movement distance)	O(1)	Simulates every move step by step
Optimal	O(n)	O(1)	Uses the maximum coordinate difference formula

Algorithm Walkthrough

1. Initialize a variable called total_time to 0.

This variable will accumulate the minimum travel time between every consecutive pair of points. 2. Iterate through the points array starting from index 1.

Each iteration considers movement from the previous point to the current point. 3. Compute the horizontal difference.

Calculate:

$$dx = |x2 - x1|$$

This represents how many horizontal moves would be required if diagonal movement did not exist. 4. Compute the vertical difference.

Calculate:

$$dy = |y2 - y1|$$

This represents how many vertical moves would be required independently. 5. Determine the minimum time for this segment.

Since one diagonal move reduces both coordinates simultaneously, the optimal strategy is to use as many diagonal moves as possible.

Therefore, the required time is:

$\max(|x_2-x_1|,|y_2-y_1|)$ 6. Add this value to total_time.

Each segment contributes independently to the final answer. 7. After processing all consecutive pairs, return total_time.

Why it works

A diagonal move reduces both horizontal and vertical distance by one simultaneously. Therefore, the optimal strategy is always to perform diagonal moves whenever both coordinates still differ.

Once one coordinate becomes aligned, only straight moves remain. The total number of moves therefore equals the larger coordinate difference, because the smaller difference can be completely absorbed by diagonal movement.

Summing this value across all consecutive point pairs gives the global minimum time.

Python Solution

from typing import List

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

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

            dx = abs(x2 - x1)
            dy = abs(y2 - y1)

            total_time += max(dx, dy)

        return total_time

The implementation begins by initializing total_time, which stores the cumulative answer.

The loop starts from index 1 because each iteration compares the current point with the previous one. We unpack both points into coordinate variables for readability.

Next, we compute the absolute horizontal and vertical differences using abs(). The minimum travel time between these two points is the larger of the two differences, since diagonal moves can reduce both dimensions simultaneously.

That value is added to total_time, and after all pairs are processed, the final answer is returned.

The solution directly mirrors the mathematical insight described earlier.

Go Solution

func minTimeToVisitAllPoints(points [][]int) int {
    totalTime := 0

    for i := 1; i < len(points); i++ {
        x1, y1 := points[i-1][0], points[i-1][1]
        x2, y2 := points[i][0], points[i][1]

        dx := abs(x2 - x1)
        dy := abs(y2 - y1)

        if dx > dy {
            totalTime += dx
        } else {
            totalTime += dy
        }
    }

    return totalTime
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

The Go implementation follows the same logic as the Python version. Since Go does not provide a built-in integer abs function in the standard library for this exact use case, we define a helper function.

Instead of using max(), the solution uses a simple conditional comparison between dx and dy.

Slices are used naturally for the input structure, and integer overflow is not a concern because the maximum possible answer is very small relative to Go's integer limits.

Worked Examples

Example 1

Input: [[1,1],[3,4],[-1,0]]

We process consecutive point pairs.

Segment 1: (1,1) to (3,4)

Variable	Value
x1	1
y1	1
x2	3
y2	4
dx	2
dy	3
segment time	3
total_time	3

Explanation:

• Two diagonal moves:

• (1,1) → (2,2)

• (2,2) → (3,3)

• One vertical move:

• (3,3) → (3,4)

Total = 3

Segment 2: (3,4) to (-1,0)

Variable	Value
x1	3
y1	4
x2	-1
y2	0
dx	4
dy	4
segment time	4
total_time	7

Explanation:

• Four diagonal moves reduce both coordinates simultaneously.

Final answer:

7

Example 2

Input: [[3,2],[-2,2]]

Segment 1: (3,2) to (-2,2)

Variable	Value
dx	5
dy	0
segment time	5
total_time	5

Since the y coordinate is already aligned, only horizontal movement is needed.

Final answer:

5

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We process each consecutive pair exactly once
Space	O(1)	Only a few variables are used

The algorithm performs a single pass through the points array. Each iteration does constant-time arithmetic operations, so the runtime grows linearly with the number of points.

No additional data structures proportional to input size are allocated, so the space complexity remains constant.

Test Cases

from typing import List

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

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

            dx = abs(x2 - x1)
            dy = abs(y2 - y1)

            total_time += max(dx, dy)

        return total_time

sol = Solution()

assert sol.minTimeToVisitAllPoints([[1,1],[3,4],[-1,0]]) == 7
# Provided example with mixed movement

assert sol.minTimeToVisitAllPoints([[3,2],[-2,2]]) == 5
# Pure horizontal movement

assert sol.minTimeToVisitAllPoints([[0,0]]) == 0
# Single point requires no movement

assert sol.minTimeToVisitAllPoints([[0,0],[0,5]]) == 5
# Pure vertical movement

assert sol.minTimeToVisitAllPoints([[0,0],[5,5]]) == 5
# Pure diagonal movement

assert sol.minTimeToVisitAllPoints([[1,1],[1,1]]) == 0
# Identical consecutive points

assert sol.minTimeToVisitAllPoints([[-1,-1],[-4,-5]]) == 4
# Negative coordinates

assert sol.minTimeToVisitAllPoints([[0,0],[1,2],[3,6]]) == 6
# Multiple segments with different movement patterns

assert sol.minTimeToVisitAllPoints([[1000,1000],[-1000,-1000]]) == 2000
# Large coordinate differences

Test	Why
[[1,1],[3,4],[-1,0]]	Validates mixed diagonal and straight movement
[[3,2],[-2,2]]	Validates horizontal-only movement
[[0,0]]	Validates single-point edge case
[[0,0],[0,5]]	Validates vertical-only movement
[[0,0],[5,5]]	Validates perfect diagonal movement
[[1,1],[1,1]]	Validates zero-distance movement
[[-1,-1],[-4,-5]]	Validates handling of negative coordinates
[[0,0],[1,2],[3,6]]	Validates cumulative multi-segment traversal
[[1000,1000],[-1000,-1000]]	Validates large coordinate ranges

Edge Cases

One important edge case is when the input contains only a single point. Since there is nowhere to move, the minimum required time is 0. A buggy implementation might incorrectly attempt to access a nonexistent previous point or assume at least one movement segment exists. This implementation handles the case naturally because the loop starts at index 1, so no iterations occur.

Another important case is when two consecutive points are identical. For example, moving from (2,2) to (2,2) requires zero seconds. Some implementations might incorrectly add one movement step or mishandle zero differences. Here, both dx and dy become 0, so max(dx, dy) is also 0.

A third important edge case occurs when movement is purely horizontal or purely vertical. For example, moving from (0,0) to (0,5) allows no diagonal movement because the x coordinate is already aligned. The formula still works correctly because the maximum difference equals the number of required straight moves.

Negative coordinates are another potential source of bugs. Since the solution always uses absolute differences, coordinate signs do not matter. Moving from (-3,-2) to (1,4) is handled exactly the same way as movement between positive coordinates.