Problem 1266

Abstract / Summary

Find the shortest time to visit all given points by moving in steps that change one coordinate at a time.

Note

The full problem description, including helpful examples, can be found on LeetCode.

Python 1266.py

class Solution:
    def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
        result = 0
        for i in range(1, len(points)):
            dx = abs(points[i][0] - points[i - 1][0])
            dy = abs(points[i][1] - points[i - 1][1])
            result += max(dx, dy)
        return result
8 lines | 318 bytes | submitted November 30, 2023 | GitHub   tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 83% (200k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Geometry
  • Math
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.
LeetCode profile | GitHub repo

Code Walkthrough

Overview

The provided implementation defines a class Solution with a single method minTimeToVisitAllPoints. The method receives a list of coordinate pairs, each representing a point on a 2-dimensional grid. The goal is to compute the minimum number of time steps required to travel sequentially through all points, moving one unit horizontally, vertically, or diagonally per step. The algorithm iterates over consecutive point pairs, calculates the horizontal and vertical distances, and aggregates the larger of the two distances for each segment. The final sum is returned as the total minimum time.

Key Steps

Initialization of the accumulator

result = 0

An integer variable result is created to hold the cumulative travel time. It starts at zero because no movement has occurred before processing the points.

Iteration over consecutive points

for i in range(1, len(points)):

The loop begins at index 1 and proceeds to the last index of the points list. By starting at 1, each iteration can safely reference the current point and its immediate predecessor, ensuring that every segment between two successive points is examined exactly once.

Computation of horizontal and vertical differences

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

For the current segment, the absolute difference in the x-coordinates (dx) and the absolute difference in the y-coordinates (dy) are calculated. The use of abs guarantees non-negative values, which aligns with the distance interpretation on a grid.

Determination of segment travel time

result += max(dx, dy)

The minimum number of steps required to move from one point to the next equals the larger of the two coordinate differences. This follows from the ability to move diagonally, which simultaneously reduces both dx and dy by one per step until one of the differences reaches zero; the remaining difference is then covered by straight moves. Adding max(dx, dy) to result accumulates the optimal travel time for the segment.

Return of the final result

return result

After processing all consecutive point pairs, the method returns the total accumulated time, representing the minimal steps needed to visit the entire sequence of points.

Edge Cases Handled

When the input list contains a single point, the loop body never executes because the range starts at 1 and the length is also 1. Consequently, result remains zero, which correctly reflects that no movement is required. If two points are identical, both dx and dy evaluate to zero, and max(dx, dy) contributes nothing to the total, preserving the correct zero-step cost for that segment. The use of abs ensures that points provided in any order, including decreasing coordinate values, are processed without negative distance values, maintaining correctness across all possible coordinate configurations.

Performance Optimizations Observed

The algorithm processes each point exactly once after the initial element, resulting in a single linear pass over the input data. By computing dx and dy directly from the coordinate pairs and immediately applying max without any intermediate data structures, the implementation minimizes memory overhead. The use of built-in arithmetic operations (abs and max) leverages highly optimized native code paths, contributing to fast execution. The accumulator result is updated in place, avoiding the creation of temporary collections or additional function calls. This combination of a single pass, in-place accumulation, and reliance on primitive operations yields an efficient solution for large point sets.

written by openai gpt

ELI5 - Simplified Explanation

Imagine you are holding a crayon and a piece of paper with dots drawn all over it in different places. This code is like a little helper that figures out the quickest way to draw a line connecting all those dots in order. First, the code starts with a total distance of zero. It looks at the first dot and the next dot, then it measures how far apart they are side to side and how far apart they are up and down. Since it is possible to draw a diagonal line, the code picks the larger of those two distances to represent the step from one dot to the next. It saves that number and adds it to the total. Then, it hops to the next dot and repeats the same process over and over until it has visited every single point on the paper. The final number ends up being the total amount of movement needed to get through all the dots.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 9 | μ = 8.67 | σ = 1.25

Complexity Analysis

Time: linear
As a rule of thumb, the maximum input size for one second execution time is
  • factorial: up to 10 elements
  • exponential: up to 20 elements
  • polynomial: a few thousand elements
  • loglinear: up to 100,000 elements
  • linear: a few million elements
  • logarithmic: a billion elements
  • constant: practically unlimited
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)
author
author solutions
www AlgoMonster C++ Python Java TS
WalkCCC C++ Python Java
leetcode.ca C++ Python Java Go C Rust TS
Progiez C++ Python Java
github BigEggStudy C#
black-shadows C++
charles-wangkai Java
DimitrisJim C
everthis JS
fartem Ruby
fpdjsns Python
fsq C++
Garvit244 Python
halfrost Go
JoshCrozier JS
keineahnung2345 C++
lkwq007 Python
suxrobGM C#
varunu28 Java
withaarzoo C++
YuriSpiridonov Python
AlgoMonster C++, Python, Java, TypeScript
WalkCCC C++, Python, Java
leetcode.ca C, C++, Go, Java, Python, Rust, TypeScript
Progiez C++, Java, Python
BigEggStudy C#
black-shadows C++, C++
charles-wangkai Java
DimitrisJim C
everthis JavaScript
fartem Ruby
fpdjsns Python
fsq C++
Garvit244 Python
halfrost Go
JoshCrozier JavaScript
keineahnung2345 C++
lkwq007 Python
suxrobGM C#
varunu28 Java
withaarzoo C++
YuriSpiridonov Python
34 links | 21 authors | 10 languages

Videos

3 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

8 solutions   November 30, 2023

Extra

There are a few extra pages giving you some insights into my setup:
  • Tech Stack - my development environment and tools
  • AI - how AI helped me create this website (NOT solving the problems)
  • Progress - progression over time
  • Quality - code quality