285. Visit Every Point
A delivery drone flies over a city grid. You receive points, a list of integer waypoints [x, y], and the drone starts on points[0]. It must reach the waypoints in the listed order. Each second it hops exactly one cell to any of the 8 surrounding cells (sideways, up, down or diagonally). It may fly over waypoints that appear later in the list without that counting as a visit, and it may linger on a cell only by hopping around, so treat each hop as one second of progress.
Return the minimum number of seconds needed to visit every waypoint in order. A single waypoint needs 0 seconds. Aim for O(n) time and O(1) extra space.
Example 1
- Input:
- points = [[2,-1],[6,4],[3,9]]
- Output:
- 10
- Explanation:
The first leg has offsets (4,5) so it takes 5 seconds, and the second has (3,5) so it takes 5 more, 10 in total.
Example 2
- Input:
- points = [[-5,5],[-5,-4],[2,3]]
- Output:
- 16
- Explanation:
A straight 9-cell drop takes 9 seconds, then offsets (7,7) take 7 diagonal seconds: 16.
Example 3
- Input:
- points = [[7,7]]
- Output:
- 0
- Explanation:
With a single waypoint there is nothing to travel to, so the time is 0.
Constraints
1 ≤ points.length ≤ 3000
-104 ≤ x, y ≤ 104
Consecutive waypoints may coincide. The answer is at most 6*107, so it fits in a 32-bit integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)