Minimum Time to Visit All Houses

Minimum Time to Visit All Houses

What is this problem about?

The Minimum Time to Visit All Houses problem gives you positions of houses on a number line. Starting from the first house, find the minimum time to visit all houses. You can move at speed 1 in either direction. This Minimum Time to Visit All Houses coding problem uses prefix sums to efficiently compute minimum traversal costs for ranges of houses.

Why is this asked in interviews?

Salesforce asks this to test the ability to translate a geometric traversal problem into a prefix sum calculation. The key observation — that visiting houses in sorted order with a single traversal (going left first then right, or right first then left) gives the optimal strategy — ties the problem to prefix sum computation. The array and prefix sum interview pattern is central.

Algorithmic pattern used

Prefix sum with sorted traversal. Sort house positions. The optimal strategy is to go in one direction first (covering all left houses), return to the start, then go in the other direction (covering all right houses) — or vice versa. Use prefix sums to quickly compute the total distance for each split point. For each possible "turning point," compute: 2 * min(left_range, right_range) + max(left_range, right_range).

Example explanation

Houses at positions: [2, 7, 4, 1, 9]. Sort: [1, 2, 4, 7, 9]. Start at house[0] = 1. All houses are to the right. Total distance = 9 - 1 = 8 (just move right).

Mixed positions: [3, -1, 5, 0] → sorted relative to start. Compute min time to visit all going right then left or left then right using prefix sums.

Common mistakes candidates make

• Not sorting houses first.
• Trying to simulate the traversal instead of using the formula.
• Forgetting that backtracking (going one way and then the other) only costs 2 * shorter_direction + longer_direction.
• Off-by-one in prefix sum indexing.

Interview preparation tip

Number-line traversal problems are solved cleanly with prefix sums after sorting. The fundamental insight: every house visited in one direction costs its distance from start; if you need to cover both directions, you backtrack the shorter one and pay it twice. Practice computing "minimum traversal cost to cover all points on a number line" — it's a recurring pattern in delivery routing, robot movement, and array traversal problems. Prefix sums make range-sum computation O(1) after O(n) preprocessing.