Medium

Minimum Time to Visit All Houses

LAB

Given house positions in order, return the total Manhattan distance needed to visit them all.

EXAMPLES

Example 1

Input
{
  "points": [
    [
      1,
      1
    ],
    [
      3,
      4
    ],
    [
      -1,
      0
    ]
  ]
}

Output
7

FUNCTION SHAPE

points: intMatrix→int

SOLUTION NOTE

Build prefix sums for both forward and backward circular paths. For each query, compute min of forward/backward distances using prefix sums.

Reveal reference solution +

pythonREFERENCE

def minTotalTime(self, forward: List[int], backward: List[int], queries: List[int]) -> int:
    n = len(forward)

    # Prefix sums for forward direction (0 -> 1 -> 2 -> ... -> n-1 -> 0)
    fwd_prefix = [0] * (n + 1)
    for i in range(n):
        fwd_prefix[i + 1] = fwd_prefix[i] + forward[i]
    total_fwd = fwd_prefix[n]

    # Prefix sums for backward direction (0 -> n-1 -> n-2 -> ... -> 1 -> 0)
    bwd_prefix = [0] * (n + 1)
    for i in range(n):
        bwd_prefix[i + 1] = bwd_prefix[i] + backward[(n - i) % n]
    total_bwd = bwd_prefix[n]

    def dist(src, dst):
        if src == dst:
            return 0
        # Forward distance
        fwd_dist = (fwd_prefix[dst] - fwd_prefix[src]) % total_fwd
        if dst < src:
            fwd_dist = total_fwd - fwd_prefix[src] + fwd_prefix[dst]
        # Backward distance
        bwd_dist = (bwd_prefix[n - dst] - bwd_prefix[n - src]) % total_bwd
        if dst > src:
            bwd_dist = total_bwd - bwd_prefix[n - src] + bwd_prefix[n - dst]
        return min(fwd_dist, bwd_dist)

    total = 0
    curr = 0
    for q in queries:
        total += dist(curr, q)
        curr = q
    return total

TimeO(n + q)

SpaceO(n)

Open on LeetCode ↗