2463. Minimum Total Distance Traveled

Array
Dynamic Programming
Sorting

TIME

O(n × m) where m = sum of factory limits

SPACE

O(n × m)

Intuition

After sorting both robots and factories by position, optimal assignments don't cross (if robot A is left of robot B, A's factory is not to the right of B's factory). This allows a DP solution.

Solution

Step 1: Sort

Sort robots and factories by position. This ensures optimal non-crossing assignments.

Step 2: Expand Factories

Convert each factory with limit L into L individual "slots" at that position. This simplifies the DP to 1-to-1 matching.

Step 3: DP

dp[i][j] = minimum distance to assign first i robots to first j factory slots

Transitions:

Don't use slot j for robot i: dp[i][j] = dp[i][j-1]
Use slot j for robot i: dp[i][j] = dp[i-1][j-1] + |robot[i-1] - slot[j-1]|

Base Cases

dp[0][j] = 0 no robots to assign
dp[i][0] = infinity for i > 0, can't assign robots without slots

Answer

dp[n][m] where n = number of robots, m = total slots

Complexity

Time: O(n × m) where m = sum of all factory limits
Space: O(n × m), can optimize to O(m)

Edge Cases

Single robot, single factory
All robots at same position
Factory with limit 0 (skip it)
Large negative/positive positions

Code

from typing import List


class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        """
        2463. Minimum Total Distance Traveled
        Time: O(n × m) where m = sum of factory limits
        Space: O(n × m)
        """
        robot.sort()
        factory.sort()

        # Expand factories into individual slots
        slots = []
        for pos, limit in factory:
            slots.extend([pos] * limit)

        n, m = len(robot), len(slots)

        # dp[i][j] = min distance to assign first i robots to first j slots
        dp = [[float('inf')] * (m + 1) for _ in range(n + 1)]

        # Base case: 0 robots need 0 distance
        for j in range(m + 1):
            dp[0][j] = 0

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                # Don't use slot j for robot i
                dp[i][j] = dp[i][j - 1]

                # Use slot j for robot i
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + abs(robot[i - 1] - slots[j - 1]))

        return dp[n][m]

import java.util.*;

/**
 * 2463. Minimum Total Distance Traveled
 * Time: O(n × m) where m = sum of factory limits
 * Space: O(n × m)
 */
class Solution {
    public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
        Collections.sort(robot);
        Arrays.sort(factory, (a, b) -> a[0] - b[0]);

        // Expand factories into individual slots
        List<Integer> slots = new ArrayList<>();
        for (int[] f : factory) {
            for (int i = 0; i < f[1]; i++) {
                slots.add(f[0]);
            }
        }

        int n = robot.size(), m = slots.size();

        // dp[i][j] = min distance to assign first i robots to first j slots
        long[][] dp = new long[n + 1][m + 1];

        // Initialize with infinity
        for (int i = 1; i <= n; i++) {
            Arrays.fill(dp[i], Long.MAX_VALUE / 2);
        }

        // Base case: 0 robots need 0 distance (dp[0][j] = 0 by default)

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // Don't use slot j for robot i
                dp[i][j] = dp[i][j - 1];

                // Use slot j for robot i
                long dist = Math.abs(robot.get(i - 1) - slots.get(j - 1));
                dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - 1] + dist);
            }
        }

        return dp[n][m];
    }
}