You get a list of integer points and must visit them in order. Each second you can move one unit horizontally, vertically, or diagonally. Return the minimum total time. For [[1,1],[3,4],[-1,0]] the answer is 7.
Between two points with gaps dx = |x2 - x1| and dy = |y2 - y1|, move diagonally for min(dx, dy) seconds, which closes both gaps at once, then straight for the rest. The total is min + (max - min) = max(dx, dy). That is the Chebyshev distance, and you cannot do better because each second reduces each gap by at most 1.
def min_time(points):
total = 0
for (x1, y1), (x2, y2) in zip(points, points[1:]):
total += max(abs(x2 - x1), abs(y2 - y1))
return totalO(n) time, O(1) extra space.
dx + dy.State the lower bound (each second shrinks each gap by at most 1) and the matching construction (diagonal first). That pair of sentences is the whole proof, and interviewers like hearing both halves.
Disclosure: I work on Linkjob.ai, which builds an AI assistant for coding and job interviews.