DDSA Solutions

1266. Minimum Time Visiting All Points

EasyView on LeetCode
ArrayMath
Time: O(n)
Space: O(1)

Problem Overview

Sum Manhattan distances between consecutive points.

Intuition

Sum Manhattan distances between consecutive points. Time = sum of max(|dx|, |dy|) for Chebyshev distance since diagonal moves cost 1.

Algorithm

  1. 1For each consecutive pair (p1, p2): add max(|p1.x-p2.x|, |p1.y-p2.y|) to total.

Common Pitfalls

  • •Movement is 8-directional (can move diagonally). Use Chebyshev distance: max(|dx|,|dy|).
1266.cs
C#
// Approach: The time to move between consecutive points is max(|dx|, |dy|) because diagonal moves are allowed.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MinTimeToVisitAllPoints(int[][] points)
    {
        int ans = 0;

        for (int i = 1; i < points.Length; ++i)
            ans += Math.Max(Math.Abs(points[i][0] - points[i - 1][0]),
                            Math.Abs(points[i][1] - points[i - 1][1]));

        return ans;
    }
}
Was this solution helpful?

Related Problems