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.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Sorting
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 100factory[j].length == 2-10^6 <= robot[i], position_j <= 10^60 <= limit_j <= robot.lengthall robot positions are distinct; all factory positions are distinctthe factories can repair every robot
Hints for Minimum Total Distance Traveled
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.
Hint 2
So let
dp[i][j]be the cheapest way to repair robotsi..using factoriesj..: either skip factoryj, or let it take the nextkrobots (1 <= k <= limit_j).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]), withdp[n][*] = 0anddp[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
- Sort
robotascending andfactoryby position. dp[i][j]= minimum total distance to repair robotsi..n-1with factoriesj..m-1;dp[n][j] = 0,dp[i][m] = ∞fori < n.- Transition:
dp[i][j] = dp[i][j+1](factoryjtakes nobody), then fork = 1..limit_jwithi + k <= n, accumulatecost += |robot[i+k-1] - pos_j|and takecost + dp[i+k][j+1]. - Fill from
i = n, j = mbackwards and returndp[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 = 0can only be skipped. - Use a 64-bit or large sentinel for 'impossible' and do not add to it —
∞ + costoverflows 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