Problem

There are some robots and factories on the X-axis. You are given an integer array robot where robot[i] is the position of the ith robot. You are also given a 2D integer array factory where factory[j] = [positionj, limitj] indicates that positionj is the position of the jth factory and that the jth factory can repair at most limitj robots.

The positions of each robot are unique. The positions of each factory are also unique. Note that a robot can be in the same position as a factory initially.

All the robots are initially broken; they keep moving in one direction. The direction could be the negative or the positive direction of the X-axis. When a robot reaches a factory that did not reach its limit, the factory repairs the robot, and it stops moving.

At any moment, you can set the initial direction of moving for some robot. Your target is to minimize the total distance traveled by all the robots.

Return the minimum total distance traveled by all the robots. The test cases are generated such that all the robots can be repaired.

Note that

  • All robots move at the same speed.
  • If two robots move in the same direction, they will never collide.
  • If two robots move in opposite directions and they meet at some point, they do not collide. They cross each other.
  • If a robot passes by a factory that reached its limits, it crosses it as if it does not exist.
  • If the robot moved from a position x to a position y, the distance it moved is |y - x|.

Examples

Example 1:

Input: robot = [0,4,6], factory = [[2,2],[6,2]]
Output: 4
Explanation: As shown in the figure:
- The first robot at position 0 moves in the positive direction. It will be repaired at the first factory.
- The second robot at position 4 moves in the negative direction. It will be repaired at the first factory.
- The third robot at position 6 will be repaired at the second factory. It does not need to move.
The limit of the first factory is 2, and it fixed 2 robots.
The limit of the second factory is 2, and it fixed 1 robot.
The total distance is |2 - 0| + |2 - 4| + |6 - 6| = 4. It can be shown that we cannot achieve a better total distance than 4.

Example 2:

Input: robot = [1,-1], factory = [[-2,1],[2,1]]
Output: 2
Explanation: As shown in the figure:
- The first robot at position 1 moves in the positive direction. It will be repaired at the second factory.
- The second robot at position -1 moves in the negative direction. It will be repaired at the first factory.
The limit of the first factory is 1, and it fixed 1 robot.
The limit of the second factory is 1, and it fixed 1 robot.
The total distance is |2 - 1| + |(-2) - (-1)| = 2. It can be shown that we cannot achieve a better total distance than 2.

Solution

Method 1 - Recursive

The task requires pairing robots with factories to minimize the total travel distance. Our goal is to find the minimal total distance for all robots to reach any factory under the given constraints.

The solution employs a dynamic programming strategy to examine whether each robot should be assigned to a particular factory or skipped. The state transitions between robots and factories help us build up the minimal distance by either assigning a robot to a factory or skipping the factory for the robot, balancing these choices optimally.

Approach

Here is the approach: Sorting Robots and Factories:

  • Sort both the robot and the factory arrays.
  • For each factory, create positions according to its repair limit in a separate array. This allows each factory position to be independently considered for each robot.

Recursive Choices:

  • The function makes two choices for each robot and factory position:
    • Pick: Assign the current robot to the current factory. The cost is the absolute difference between their positions, plus the result of solving for the next robot and factory position.
    • Not Pick: Skip the current factory for the current robot and move to the previous factory position without moving the robot position forward.

Base Cases:

  • No Robots Left: If all robots have been assigned, return 0 since there is no more distance to cover.
  • No Factories Left: If no factories are left to assign while robots remain, return a very large number to indicate that this path is invalid.

Recursive Relation:

  • The function returns the minimum of the pick and not pick options, ensuring the optimal minimal travel distance.

Code

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

        List<Integer> expandedFactories = new ArrayList<>();
        for (int[] f : factory) {
            int position = f[0];
            int limit = f[1];
            for (int i = 0; i < limit; i++) {
                expandedFactories.add(position);
            }
        }

        return solve(0, 0, robot.toArray(new Integer[0]), expandedFactories.toArray(new Integer[0]));
    }

    private long solve(int roboPos, int factPos, Integer[] robots, Integer[] factories) {
        if (roboPos == robots.length) {
            return 0;
        }
        if (factPos == factories.length) {
            return Long.MAX_VALUE;
        }

        long pick = Math.abs(robots[roboPos] - factories[factPos]) + solve(roboPos + 1, factPos + 1, robots, factories);
        long notPick = solve(roboPos, factPos + 1, robots, factories);

        return Math.min(pick, notPick);
    }
}
Python
class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        robot.sort()
        factory.sort(key=lambda x: x[0])

        expanded_factories = []
        for f in factory:
            pos, limit = f[0], f[1]
            for _ in range(limit):
                expanded_factories.append(pos)

        def solve(roboPos: int, factPos: int) -> int:
            if roboPos == len(robot):
                return 0  # All robots assigned
            if factPos == len(expanded_factories):
                return float('inf')  # No more factories to assign robots to

            # Pick: assign the current robot to the current factory
            pick = abs(robot[roboPos] - expanded_factories[factPos]) + solve(roboPos + 1, factPos + 1)
            # Not Pick: skip the current factory for this robot
            notPick = solve(roboPos, factPos + 1)

            return min(pick, notPick)

        return solve(0, 0)

Complexity

  • ⏰ Time complexity: O(2 ^ (m + n)) where m is number of robots and n is number of factories
  • 🧺 Space complexity: O(m) due to the recursion stack

Method 2 - Memoization

Code

Java
public class Solution {
    private Map<String, Long> memo;

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

        List<Integer> expandedFactories = new ArrayList<>();
        for (int[] f : factory) {
            int position = f[0];
            int limit = f[1];
            for (int i = 0; i < limit; i++) {
                expandedFactories.add(position);
            }
        }

        memo = new HashMap<>();
        return solve(0, 0, robot.toArray(new Integer[0]), expandedFactories.toArray(new Integer[0]));
    }

    private long solve(int roboPos, int factPos, Integer[] robots, Integer[] factories) {
        if (roboPos == robots.length) {
            return 0;
        }
        if (factPos == factories.length) {
            return Long.MAX_VALUE;
        }

        String key = roboPos + "," + factPos;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }

        long pick = Math.abs(robots[roboPos] - factories[factPos]) + solve(roboPos + 1, factPos + 1, robots, factories);
        long notPick = solve(roboPos, factPos + 1, robots, factories);

        long result = Math.min(pick, notPick);
        memo.put(key, result);
        return result;
    }
}
Python
class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        robot.sort()
        factory.sort(key=lambda x: x[0])

        expanded_factories = []
        for f in factory:
            pos, limit = f[0], f[1]
            for _ in range(limit):
                expanded_factories.append(pos)

        memo = {}

        def solve(roboPos: int, factPos: int) -> int:
            if roboPos == len(robot):
                return 0
            if factPos == len(expanded_factories):
                return float('inf')

            if (roboPos, factPos) in memo:
                return memo[(roboPos, factPos)]

            pick = abs(robot[roboPos] - expanded_factories[factPos]) + solve(roboPos + 1, factPos + 1)
            notPick = solve(roboPos, factPos + 1)

            memo[(roboPos, factPos)] = min(pick, notPick)
            return memo[(roboPos, factPos)]

        return solve(0, 0)

Complexity

  • ⏰ Time complexity: O(m * n)
    • With memoization, each state (roboPos, factPos) is computed only once, resulting in m * n states
  • 🧺 Space complexity: O(m * n) formemoization table and recursion stack.

Method 3 - Using Bottom up DP with Tabulation

Here is the approach:: Sorting Robots and Factories:

  • First, sort both the robot array and the factory array.
  • For each factory, generate positions according to its limit and store these in a separate array, fact. This allows each factory position to be considered individually for each robot.

Dynamic Programming (DP):

  • Define dp[roboPos][factPos] to be the minimum travel distance needed to assign the first roboPos robots to the first factPos factories.

Base Cases:

  • dp[0][factPos] = 0: No robots need zero distance.
  • dp[roboPos][0] will be set to a large number because assigning robots without factories is not feasible.

Transition:

  • Pick: Assign the roboPos-1-th robot to the factPos-1-th factory. The cost is the distance from the robot to the factory plus dp[roboPos - 1][factPos - 1].
  • Not Pick: Skip the current factory for this robot, so the value is simply dp[roboPos][factPos - 1].
  • Choose the minimum between pick and not pick.

Final Solution:

  • After filling in the DP table, the solution will be located at dp[n][m], where n is the number of robots and m is the number of factories.

Code

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

        List<Integer> expandedFactories = new ArrayList<>();
        for (int[] f : factory) {
            int position = f[0];
            int limit = f[1];
            for (int i = 0; i < limit; i++) {
                expandedFactories.add(position);
            }
        }

        int m = robot.size();
        int n = expandedFactories.size();

        long[][] dp = new long[m + 1][n + 1];
        for (long[] row : dp) {
            Arrays.fill(row, Long.MAX_VALUE / 10);
        }

        for (int factPos = 0; factPos <= n; factPos++) {
            dp[0][factPos] = 0;
        }

        for (int roboPos = 1; roboPos <= m; roboPos++) {
            for (int factPos = 1; factPos <= n; factPos++) {
                long pick = Math.abs(robot.get(roboPos - 1) - expandedFactories.get(factPos - 1)) +
                            dp[roboPos - 1][factPos - 1];
                long notPick = dp[roboPos][factPos - 1];
                dp[roboPos][factPos] = Math.min(pick, notPick);
            }
        }

        return dp[m][n];
    }
}
Python
class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        # Sort robots and factories by position
        robot.sort()
        factory.sort(key=lambda x: x[0])

        # Expand factory positions based on their limit
        expanded_factories = []
        for f in factory:
            pos, limit = f[0], f[1]
            for _ in range(limit):
                expanded_factories.append(pos)

        n = len(robot)
        m = len(fact)

        # Initialize DP table with large values
        dp = [[float('inf')] * (m + 1) for _ in range(n + 1)]
        
        # Base case: no robots require zero distance
        for factPos in range(m + 1):
            dp[0][factPos] = 0

        # Fill the DP table
        for roboPos in range(1, n + 1):
            for factPos in range(1, m + 1):
                pick = abs(robot[roboPos - 1] - expanded_factories[factPos - 1]) + dp[roboPos - 1][factPos - 1]
                notPick = dp[roboPos][factPos - 1]
                dp[roboPos][factPos] = min(pick, notPick)
        
        return dp[n][m]

Complexity

  • ⏰ Time complexity: O(m * n)
  • 🧺 Space complexity: O(m * n)