Minimum Total Distance Traveled

Hard
1632.

Minimum Total Distance Traveled

Minimum Total Distance Traveled is a hard coding problem on arrays, dynamic programming and sorting, asked in Amazon and Google interviews.

Robots and factories sit on a number line. robot[i] is the position of robot i, and factory[j] = [position_j, limit_j] says factory j is at position_j and can repair at most limit_j robots. Every robot is broken.

You choose, for each robot, a direction to move (left or right). A robot moves until it reaches a factory that still has capacity; that factory repairs it and the robot stops. Robots move at the same speed and never collide. Equivalently, you assign every robot to a factory, respecting the limits, and the robot travels the distance between them.

Return the minimum total distance traveled by all robots. The input guarantees that every robot can be repaired.

CodeKairo note: positions here lie in [-10^6, 10^6] (the original allows ±10^9), so the answer always fits in a 32-bit integer.

Example 1

Input
robot = [0,4,6], factory = [[2,2],[6,2]]
Output
4
Explanation
Robot at 0 goes to 2 (distance 2), robot at 4 goes to 2 (distance 2), robot at 6 is already at the factory at 6: total 4.

Example 2

Input
robot = [1,-1], factory = [[-2,1],[2,1]]
Output
2
Explanation
Robot at 1 goes to 2 and robot at -1 goes to -2: total 2.

Example 3

Input
robot = [5], factory = [[5,1]]
Output
0

Constraints

  • 1 <= robot.length, factory.length <= 100
  • factory[j].length == 2
  • -10^6 <= robot[i], position_j <= 10^6
  • 0 <= limit_j <= robot.length
  • all robot positions are distinct; all factory positions are distinct
  • the factories can repair every robot
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} robot
 * @param {number[][]} factory
 * @return {number}
 */
var minimumTotalDistance = function(robot, factory) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Total Distance Traveled — Problem & Solution

Minimum Total Distance Traveled solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Total Distance Traveled is a hard coding problem on arrays, dynamic programming and sorting, asked in Amazon and Google interviews.

Problem statement

Robots and factories sit on a number line. robot[i] is the position of robot i, and factory[j] = [position_j, limit_j] says factory j is at position_j and can repair at most limit_j robots. Every robot is broken.

You choose, for each robot, a direction to move (left or right). A robot moves until it reaches a factory that still has capacity; that factory repairs it and the robot stops. Robots move at the same speed and never collide. Equivalently, you assign every robot to a factory, respecting the limits, and the robot travels the distance between them.

Return the minimum total distance traveled by all robots. The input guarantees that every robot can be repaired.

CodeKairo note: positions here lie in [-10^6, 10^6] (the original allows ±10^9), so the answer always fits in a 32-bit integer.

Example 1

Input: robot = [0,4,6], factory = [[2,2],[6,2]]
Output: 4
Explanation: Robot at 0 goes to 2 (distance 2), robot at 4 goes to 2 (distance 2), robot at 6 is already at the factory at 6: total 4.

Example 2

Input: robot = [1,-1], factory = [[-2,1],[2,1]]
Output: 2
Explanation: Robot at 1 goes to 2 and robot at -1 goes to -2: total 2.

Example 3

Input: robot = [5], factory = [[5,1]]
Output: 0

Constraints

  • 1 <= robot.length, factory.length <= 100
  • factory[j].length == 2
  • -10^6 <= robot[i], position_j <= 10^6
  • 0 <= limit_j <= robot.length
  • all robot positions are distinct; all factory positions are distinct
  • the factories can repair every robot

Hints for Minimum Total Distance Traveled

  1. Hint 1

    Sort robots and factories by position. In some optimal assignment, the robots served by each factory form a contiguous block in sorted order, and the blocks go to factories left to right.

  2. Hint 2

    So let dp[i][j] be the cheapest way to repair robots i.. using factories j..: either skip factory j, or let it take the next k robots (1 <= k <= limit_j).

  3. Hint 3

    dp[i][j] = min(dp[i][j+1], min over k of (Σ |robot[i+t] - pos_j| for t < k) + dp[i+k][j+1]), with dp[n][*] = 0 and dp[i<n][m] = ∞.

How to solve Minimum Total Distance Traveled

After sorting, crossing assignments are never better than uncrossed ones, so each factory serves a contiguous run of robots in order. That turns the assignment problem into a two-pointer DP over (next robot, next factory).

Approach

  1. Sort robot ascending and factory by position.
  2. dp[i][j] = minimum total distance to repair robots i..n-1 with factories j..m-1; dp[n][j] = 0, dp[i][m] = ∞ for i < n.
  3. Transition: dp[i][j] = dp[i][j+1] (factory j takes nobody), then for k = 1..limit_j with i + k <= n, accumulate cost += |robot[i+k-1] - pos_j| and take cost + dp[i+k][j+1].
  4. Fill from i = n, j = m backwards and return dp[0][0].

Why it works

If robot a < b were assigned to factories x > y, swapping their factories never increases |a - x| + |b - y| (an exchange argument on the number line), so some optimal assignment is order-preserving. In such an assignment factory j takes a contiguous block right after the robots taken by factories before it, which is exactly what the DP enumerates.

Complexity

  • Time — O(n * m * n) in the worst case (the inner loop is bounded by each limit)
  • Space — O(n * m)

Pitfalls

  • A factory with limit = 0 can only be skipped.
  • Use a 64-bit or large sentinel for 'impossible' and do not add to it — ∞ + cost overflows a 32-bit int.
  • The movement story (directions, factories passed by) is a distraction: a robot can always walk past full factories, so any capacity-respecting assignment is achievable.

Reference solution

Python

from typing import List

def minimumTotalDistance(robot: List[int], factory: List[List[int]]) -> int:
    r = sorted(robot)
    f = sorted(factory)
    n, m = len(r), len(f)
    INF = float('inf')
    dp = [[INF] * (m + 1) for _ in range(n + 1)]
    for j in range(m + 1):
        dp[n][j] = 0
    for j in range(m - 1, -1, -1):
        pos, limit = f[j]
        for i in range(n - 1, -1, -1):
            best = dp[i][j + 1]
            cost = 0
            for k in range(1, limit + 1):
                if i + k > n:
                    break
                cost += abs(r[i + k - 1] - pos)
                cand = cost + dp[i + k][j + 1]
                if cand < best:
                    best = cand
            dp[i][j] = best
    return dp[0][0]

Java

public static int minimumTotalDistance(int[] robot, int[][] factory) {
    int[] r = robot.clone();
    Arrays.sort(r);
    int[][] f = factory.clone();
    Arrays.sort(f, (a, b) -> Integer.compare(a[0], b[0]));
    int n = r.length, m = f.length;
    final long INF = Long.MAX_VALUE / 4;
    long[][] dp = new long[n + 1][m + 1];
    for (int i = 0; i < n; i++) Arrays.fill(dp[i], INF);
    for (int j = m - 1; j >= 0; j--) {
        int pos = f[j][0], limit = f[j][1];
        for (int i = n - 1; i >= 0; i--) {
            long best = dp[i][j + 1], cost = 0;
            for (int k = 1; k <= limit && i + k <= n; k++) {
                cost += Math.abs(r[i + k - 1] - pos);
                best = Math.min(best, cost + dp[i + k][j + 1]);
            }
            dp[i][j] = best;
        }
    }
    return (int) dp[0][0];
}

C++

int minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
    vector<int> r = robot;
    sort(r.begin(), r.end());
    vector<vector<int>> f = factory;
    sort(f.begin(), f.end());
    int n = r.size(), m = f.size();
    const long long INF = LLONG_MAX / 4;
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, INF));
    for (int j = 0; j <= m; j++) dp[n][j] = 0;
    for (int j = m - 1; j >= 0; j--) {
        int pos = f[j][0], limit = f[j][1];
        for (int i = n - 1; i >= 0; i--) {
            long long best = dp[i][j + 1], cost = 0;
            for (int k = 1; k <= limit && i + k <= n; k++) {
                cost += abs(r[i + k - 1] - pos);
                best = min(best, cost + dp[i + k][j + 1]);
            }
            dp[i][j] = best;
        }
    }
    return (int)dp[0][0];
}

JavaScript

var minimumTotalDistance = function(robot, factory) {
    var r = robot.slice().sort(function(a, b) { return a - b; });
    var f = factory.slice().sort(function(a, b) { return a[0] - b[0]; });
    var n = r.length, m = f.length, INF = Infinity, dp = [];
    for (var i = 0; i <= n; i++) dp.push(new Array(m + 1).fill(i === n ? 0 : INF));
    for (var j = m - 1; j >= 0; j--) {
        var pos = f[j][0], limit = f[j][1];
        for (var i = n - 1; i >= 0; i--) {
            var best = dp[i][j + 1], cost = 0;
            for (var k = 1; k <= limit && i + k <= n; k++) {
                cost += Math.abs(r[i + k - 1] - pos);
                if (cost + dp[i + k][j + 1] < best) best = cost + dp[i + k][j + 1];
            }
            dp[i][j] = best;
        }
    }
    return dp[0][0];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming