Minimum Total Distance Traveled

Video solution

What this problem is really about

The movement story sounds complicated, but the collisions do not actually matter here.

Robots moving in opposite directions can pass through each other, and robots moving in the same direction never interfere. So the problem reduces to this:

• assign every robot to some factory
• respect each factory capacity
• minimize total absolute distance

Key observation

After sorting robots and factories by position, an optimal assignment never needs to "cross".

That means if a robot on the left uses some factory slot, then a robot on the right will only use the same slot or a later slot in sorted order. Once we expand each factory into repeated positions based on its repair limit, the problem becomes:

• match sorted robots
• to sorted factory slots
• while keeping the order increasing

This is the exact setup where dynamic programming works nicely.

Approach

1. Sort everything

Sort robot and sort factory by position.

2. Flatten factory capacity into slots

If a factory is at position 6 and can repair 3 robots, treat it like three identical slots:

[6, 6, 6]

So if factories are:

[[2, 2], [6, 2]]

the flattened slot list becomes:

[2, 2, 6, 6]

Now each robot only needs to choose one slot.

3. DP state

Let dp[i][j] be the minimum total distance needed to repair robots starting from index i using factory slots starting from index j.

At (i, j), we have two choices:

1. assign robot i to slot j
2. skip slot j

So the recurrence is:

dp[i][j] = min(
    |robot[i] - slot[j]| + dp[i + 1][j + 1],
    dp[i][j + 1]
)

Base cases:

• if no robots are left, answer is 0
• if robots are left but no slots are left, answer is infinity

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Solution {
    public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
        Collections.sort(robot);
        Arrays.sort(factory, Comparator.comparingInt(a -> a[0]));

        int robotCount = robot.size();
        List<Integer> factoryPositions = new ArrayList<>();

        for (int[] currentFactory : factory) {
            int copies = Math.min(currentFactory[1], robotCount);
            for (int i = 0; i < copies; i++) {
                factoryPositions.add(currentFactory[0]);
            }
        }

        int slotCount = factoryPositions.size();
        long[][] dp = new long[robotCount + 1][slotCount + 1];
        long inf = Long.MAX_VALUE / 4;

        for (int i = 0; i < robotCount; i++) {
            dp[i][slotCount] = inf;
        }

        for (int i = robotCount - 1; i >= 0; i--) {
            for (int j = slotCount - 1; j >= 0; j--) {
                long assign =
                    Math.abs((long) robot.get(i) - factoryPositions.get(j)) +
                    dp[i + 1][j + 1];
                long skip = dp[i][j + 1];
                dp[i][j] = Math.min(assign, skip);
            }
        }

        return dp[0][0];
    }
}

Dry run

Take:

robot = [0, 4, 6]
factory = [[2, 2], [6, 2]]

After sorting:

robot = [0, 4, 6]
slots = [2, 2, 6, 6]

Now think in terms of slots:

• robot 0 can use slot 2
• robot 4 can use the next slot 2
• robot 6 can use slot 6

Total distance:

|0 - 2| + |4 - 2| + |6 - 6| = 2 + 2 + 0 = 4

The DP checks all valid ways to either use or skip each slot and confirms that 4 is the minimum.

Why the recurrence works

At every state (i, j), slot j is the earliest slot we still have available.

• If we use it for robot i, both indices move forward.
• If we skip it, only the slot index moves forward.

Because both arrays are sorted and we keep assignments in order, every valid solution can be represented by these two choices.

That is why the tabulation is complete and correct.

Complexity

Let:

• r = number of robots
• s = total flattened factory slots, where s = sum(min(limit_j, r))

Then:

• Time: O(r log r + f log f + r * s)
• Space: O(r * s)

Since s <= f * r, the worst-case DP bound is O(f * r^2).

Common mistakes

1. Overthinking collisions

The crossing and direction rules are only there to tell us robots do not block one another. This is an assignment DP, not a simulation problem.

2. Forgetting to sort first

Without sorting, the "assign or skip" recurrence is not valid.

3. Using a small infinity value

The total answer can be large, so use long, long long, or i64 style types.

Interview takeaway

The clean mental model is:

convert factory capacities into sorted slots, then do ordered matching with DP.

Once that clicks, the hard-looking movement description becomes a very manageable tabulation problem.