# Minimum Total Distance Traveled
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-total-distance-traveled)
Canonical: https://scaleengineer.com/dsa/problems/minimum-total-distance-traveled
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## 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|`.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-total-distance-traveled/image0.jpg) 

**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:**

![](https://assets.glich.co/dsa/minimum-total-distance-traveled/image1.jpg) 

**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.

**Constraints:**

* `1 <= robot.length, factory.length <= 100`
* `factory[j].length == 2`
* `-109 <= robot[i], positionj <= 109`
* `0 <= limitj <= robot.length`
* The input will be generated such that it is always possible to repair every robot.

# Approaches
## Bottom-Up Dynamic Programming
A key observation for this problem is the **non-crossing property**. If we sort both the robot and factory positions, an optimal assignment of robots to factories will not have any "crossings". This means if robot `r_i` is assigned to factory `f_k` and robot `r_j` (where `r_i < r_j`) is assigned to factory `f_l`, then in an optimal solution, we can always ensure `f_k <= f_l`. This property drastically reduces the search space and allows for a dynamic programming solution.

We can define a DP state `dp[i][j]` as the minimum total distance to repair the first `i` sorted robots using the first `j` sorted factories. To compute `dp[i][j]`, we consider the `j`-th factory. We can either not use it (in which case the cost is `dp[i][j-1]`), or use it to repair some number `k` of the last robots (`robot[i-k]` to `robot[i-1]`), provided `k` does not exceed the factory's limit. The cost for the latter case would be the cost to repair the first `i-k` robots with the first `j-1` factories (`dp[i-k][j-1]`) plus the travel distance for those `k` robots to the `j`-th factory. We take the minimum over all valid choices.
**Time:** O(n * m^2). We have two outer loops for `j` (factories, size `n`) and `i` (robots, size `m`). The inner loop for `k` (robots assigned to the current factory) can run up to `m` times. Sorting takes O(m log m + n log n). · **Space:** O(m * n), where `m` is the number of robots and `n` is the number of factories. This is for the 2D DP table.
**Pros:** The logic is a direct translation of the recurrence relation, making it relatively straightforward to understand and implement.; It correctly solves the problem by leveraging the non-crossing property.
**Cons:** The space complexity of O(m*n) might be large if the number of robots and factories is very high, although it's acceptable for the given constraints.
### Explanation
First, we sort the `robot` positions and the `factory` positions in ascending order. This ordering is essential for the DP state definition and the non-crossing property.

We use a 2D array `dp[m+1][n+1]`, where `dp[i][j]` represents the minimum cost to fix the first `i` robots (from the sorted `robot` array) using the first `j` factories (from the sorted `factory` array).

The base cases for the DP are:
*   `dp[0][j] = 0` for `0 <= j <= n`: The cost to repair zero robots is always zero, regardless of the number of factories available.
*   `dp[i][0] = infinity` for `1 <= i <= m`: It's impossible to repair any robot if there are no factories.

We then iterate through the factories from `j = 1` to `n` and for each factory, we iterate through the number of robots `i = 1` to `m`. For each `dp[i][j]`, we calculate its value based on the following recurrence relation:

`dp[i][j] = min(dp[i][j-1], dp[i-k][j-1] + cost_for_k_robots)`

Here's the breakdown:
*   `dp[i][j-1]`: This term represents the case where we do not use the `j`-th factory to repair any of the first `i` robots. The problem is reduced to repairing `i` robots with `j-1` factories.
*   `dp[i-k][j-1] + cost_for_k_robots`: This represents using the `j`-th factory to repair the last `k` robots (i.e., `robot[i-k], ..., robot[i-1]`). The number of robots `k` can range from 1 up to the `j`-th factory's limit and also cannot exceed `i`. The cost for this is the sum of the minimum cost to repair the first `i-k` robots with `j-1` factories (`dp[i-k][j-1]`) and the total distance for these `k` robots to travel to the `j`-th factory's position.

We iterate through all possible values of `k` and take the minimum to find `dp[i][j]`. The final answer is the value in `dp[m][n]`, which is the minimum cost to repair all `m` robots using all `n` factories.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public long minimumTotalDistance(int[] robot, int[][] factory) {
        int m = robot.length;
        int n = factory.length;

        Arrays.sort(robot);
        Arrays.sort(factory, Comparator.comparingInt(a -> a[0]));

        // dp[i][j]: min distance for first i robots using first j factories
        long[][] dp = new long[m + 1][n + 1];

        // Initialize dp table with a large value
        for (int i = 0; i <= m; i++) {
            Arrays.fill(dp[i], Long.MAX_VALUE / 2);
        }

        // Base case: 0 robots need 0 distance
        for (int j = 0; j <= n; j++) {
            dp[0][j] = 0;
        }

        for (int j = 1; j <= n; j++) {
            int factoryPos = factory[j - 1][0];
            int factoryLimit = factory[j - 1][1];
            for (int i = 1; i <= m; i++) {
                // Option 1: Don't use factory j-1
                dp[i][j] = dp[i][j - 1];

                // Option 2: Use factory j-1 to repair last k robots
                long cost = 0;
                for (int k = 1; k <= Math.min(i, factoryLimit); k++) {
                    // robot i-1, i-2, ..., i-k
                    cost += Math.abs((long)robot[i - k] - factoryPos);
                    dp[i][j] = Math.min(dp[i][j], dp[i - k][j - 1] + cost);
                }
            }
        }

        return dp[m][n];
    }
}
```
### Algorithm
*   Sort the `robot` array and the `factory` array (based on position).
*   Create a 2D DP table `dp` of size `(m+1) x (n+1)`, where `m` is the number of robots and `n` is the number of factories.
*   `dp[i][j]` will store the minimum total distance to repair the first `i` robots using the first `j` factories.
*   Initialize `dp[0][j] = 0` for all `j` (0 robots require 0 distance) and `dp[i][0] = infinity` for `i > 0` (robots cannot be repaired with 0 factories).
*   Iterate through each factory `j` from 1 to `n`.
*   For each factory, iterate through each robot count `i` from 1 to `m`.
*   The value `dp[i][j]` is determined by considering two possibilities for the `j`-th factory:
    1.  **Don't use factory `j`**: The cost is `dp[i][j-1]`.
    2.  **Use factory `j`**: Assign the last `k` robots (from `robot[i-k]` to `robot[i-1]`) to factory `j`. This is possible for `1 <= k <= min(i, limit_j)`. The cost is `dp[i-k][j-1]` plus the sum of distances for these `k` robots to factory `j`'s position.
*   The transition is: `dp[i][j] = min(dp[i][j-1], min_{1 <= k <= min(i, limit_j)} (dp[i-k][j-1] + cost(i, j, k)))`.
*   The final answer is `dp[m][n]`.

## Space-Optimized Bottom-Up Dynamic Programming
This approach is an optimization of the previous bottom-up DP solution. We can notice that the computation for the current factory `j` (i.e., column `j` in the 2D DP table) only depends on the results from the immediately preceding factory `j-1` (column `j-1`). This dependency allows us to reduce the space complexity from `O(m*n)` to `O(m)`.

Instead of a 2D table, we use a 1D array `dp` of size `m+1`. `dp[i]` will store the minimum cost for the first `i` robots. As we iterate through the factories, we update this `dp` array. To ensure that when we calculate the new value for `dp[i]` using factory `j`, we are using the results from factory `j-1` for `dp[i-k]`, we must iterate `i` from `m` down to `1`. This way, when `dp[i]` is updated, the values `dp[0...i-1]` still hold the results from the previous factory, which is what the recurrence relation requires.
**Time:** O(n * m^2). The time complexity is dominated by the three nested loops and is identical to the previous approach. Sorting takes O(m log m + n log n). · **Space:** O(m), where `m` is the number of robots. This is for the 1D DP array.
**Pros:** Highly memory efficient, using only O(m) space.; Maintains the same time complexity as the unoptimized version.
**Cons:** The logic for the in-place update, specifically the backward iteration for `i`, can be slightly less intuitive to grasp compared to the 2D DP table approach.
### Explanation
The core logic remains the same as the standard bottom-up DP, but we optimize the memory usage. We maintain a single 1D array `dp` of size `m+1`.

After sorting `robot` and `factory` arrays, we initialize `dp[0] = 0` and the rest of `dp` to a large value representing infinity.

We then loop through each factory `j` from 1 to `n`. For each factory, we want to update the `dp` array to incorporate the possibility of using this factory. The key is the order of updates. The update rule is:

`dp[i] = min(dp[i], dp[i-k] + cost)`

If we were to iterate `i` from 1 to `m`, when we compute the new `dp[i]`, the value `dp[i-k]` might have already been updated in the current iteration for factory `j`. This would be incorrect, as `dp[i-k]` should reflect the state *before* considering factory `j`.

To solve this, we iterate `i` in reverse, from `m` down to 1. When we compute the new `dp[i]`, we access `dp[i-k]`. Since `i-k < i`, `dp[i-k]` has not yet been updated for the current factory `j` and still holds the value from the iteration for factory `j-1`. The old value of `dp[i]` (before the inner `k` loop) also correctly represents the cost of repairing `i` robots using factories up to `j-1`.

After iterating through all factories, `dp[m]` will contain the minimum total distance to repair all `m` robots.

```java
import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public long minimumTotalDistance(int[] robot, int[][] factory) {
        int m = robot.length;
        int n = factory.length;

        Arrays.sort(robot);
        Arrays.sort(factory, Comparator.comparingInt(a -> a[0]));

        // dp[i]: min distance for first i robots
        long[] dp = new long[m + 1];
        Arrays.fill(dp, Long.MAX_VALUE / 2);
        dp[0] = 0;

        for (int j = 1; j <= n; j++) {
            int factoryPos = factory[j - 1][0];
            int factoryLimit = factory[j - 1][1];
            
            // Iterate i from m down to 1 to ensure dp[i-k] is from the previous (j-1) iteration.
            for (int i = m; i >= 1; i--) {
                long cost = 0;
                for (int k = 1; k <= Math.min(i, factoryLimit); k++) {
                    cost += Math.abs((long)robot[i - k] - factoryPos);
                    dp[i] = Math.min(dp[i], dp[i - k] + cost);
                }
            }
        }

        return dp[m];
    }
}
```
### Algorithm
*   Sort the `robot` and `factory` arrays as in the previous approach.
*   Create a 1D DP array `dp` of size `m+1`.
*   `dp[i]` will store the minimum total distance to repair the first `i` robots.
*   Initialize `dp[0] = 0` and `dp[i > 0] = infinity`.
*   Iterate through each factory `j` from 1 to `n`.
*   For each factory, iterate backwards through the robot count `i` from `m` down to 1. This backward iteration is crucial for the in-place update.
*   Inside the loop for `i`, iterate `k` from 1 to `min(i, limit_j)`.
*   Update `dp[i]` using the formula: `dp[i] = min(dp[i], dp[i-k] + cost)`. Here, `dp[i]` on the right side holds the value from the previous factory's iteration, and `dp[i-k]` also holds a value from the previous factory's iteration because `i-k < i`.
*   The final answer is `dp[m]`.

# Solutions
### Java

```java
class Solution {
private
  long[][] f;
private
  List<Integer> robot;
private
  int[][] factory;
public
  long minimumTotalDistance(List<Integer> robot, int[][] factory) {
    Collections.sort(robot);
    Arrays.sort(factory, (a, b)->a[0] - b[0]);
    this.robot = robot;
    this.factory = factory;
    f = new long[robot.size()][factory.length];
    return dfs(0, 0);
  }
private
  long dfs(int i, int j) {
    if (i == robot.size()) {
      return 0;
    }
    if (j == factory.length) {
      return Long.MAX_VALUE / 1000;
    }
    if (f[i][j] != 0) {
      return f[i][j];
    }
    long ans = dfs(i, j + 1);
    long t = 0;
    for (int k = 0; k < factory[j][1]; ++k) {
      if (i + k == robot.size()) {
        break;
      }
      t += Math.abs(robot.get(i + k) - factory[j][0]);
      ans = Math.min(ans, t + dfs(i + k + 1, j + 1));
    }
    f[i][j] = ans;
    return ans;
  }
}

```

### CPP

```cpp
using ll = long long ; class Solution { public: long long minimumTotalDistance ( vector < int >& robot , vector < vector < int >>& factory ) { sort ( robot . begin (), robot . end ()); sort ( factory . begin (), factory . end ()); vector < vector < ll >> f ( robot . size (), vector < ll > ( factory . size ())); function < ll ( int i , int j ) > dfs = [ & ]( int i , int j ) -> ll { if ( i == robot . size ()) return 0 ; if ( j == factory . size ()) return 1e15 ; if ( f [ i ][ j ]) return f [ i ][ j ]; ll ans = dfs ( i , j + 1 ); ll t = 0 ; for ( int k = 0 ; k < factory [ j ][ 1 ]; ++ k ) { if ( i + k >= robot . size ()) break ; t += abs ( robot [ i + k ] - factory [ j ][ 0 ]); ans = min ( ans , t + dfs ( i + k + 1 , j + 1 )); } f [ i ][ j ] = ans ; return ans ; }; return dfs ( 0 , 0 ); } };
```

### Python

```python
class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int: @ cache def dfs(i, j): if i == len(robot): return 0 if j == len(factory): return inf ans = dfs(i, j + 1) t = 0 for k in range(factory[j][1]): if i + k == len(robot): break t += abs(robot[i + k] - factory[j][0]) ans = min(ans, t + dfs(i + k + 1, j + 1)) return ans robot . sort() factory . sort() ans = dfs(0, 0) dfs . cache_clear() return ans

```