LeetCode 2463 - Minimum Total Distance Traveled

Here is a comprehensive, reference-quality solution guide for LeetCode 2463 - Minimum Total Distance Traveled following your formatting requirements.

leetcodehardarraydynamic-programmingsorting

LeetCode Problem 2463

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Sorting

Solution

Here is a comprehensive, reference-quality solution guide for LeetCode 2463 - Minimum Total Distance Traveled following your formatting requirements.

Problem Understanding

The problem gives us a set of robots on an X-axis, each at a unique position, and a set of factories, each at a unique position with a maximum capacity of robots it can repair. Robots are initially broken, and you can set their initial movement direction along the X-axis. When a robot reaches a factory that has not yet reached its repair limit, the robot is repaired and stops moving. The goal is to assign robots to factories and directions in a way that minimizes the total distance traveled by all robots.

The input consists of:

  • robot: an array of integers representing the positions of robots. Each position is unique.
  • factory: a 2D array [[positionj, limitj]] representing factory positions and the maximum number of robots they can repair.

The output is a single integer representing the minimum total distance all robots travel to reach factories.

Constraints and Observations:

  • The number of robots and factories is small (<= 100), so algorithms with polynomial complexity in these dimensions are acceptable.
  • Robot and factory positions can be negative or positive and may be very large in magnitude (-10^9 to 10^9).
  • It is guaranteed that all robots can be repaired, so we do not need to handle impossible scenarios.
  • Robots can move past factories if the factory is at capacity.
  • Robots can move in either direction along the X-axis; this allows flexibility in assignment.

Edge considerations include: robots starting at the same position as a factory, factories with zero capacity, and robots needing to move in opposite directions to minimize total distance.

Approaches

Brute-Force Approach:

A naive approach is to consider all permutations of robot assignments to factories. For each permutation, calculate the total distance while respecting the factory limits. This is guaranteed to give the correct answer because it explores all possibilities, but the complexity is factorial in the number of robots (O(n!)) and quickly becomes intractable for n = 100.

Optimal Approach - Dynamic Programming:

The key observation is that both robot and factory positions can be sorted along the X-axis, allowing a structured assignment from left to right. Once sorted, we can use dynamic programming to compute the minimum distance efficiently.

Define dp[i][j] as the minimum total distance to assign the first i robots to the first j factories. For each factory, you can assign k robots (up to the factory limit), and you update the dp value using the sum of distances for those k robots. This avoids exploring all permutations explicitly.

Why DP Works: Sorting ensures that assigning robots to factories in increasing order does not miss an optimal configuration. The problem reduces to combining subproblems of assigning subsets of robots to factories, which dynamic programming handles efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n!) Explore all permutations of robot-factory assignments
Dynamic Programming O(m * n^2) O(m * n) m = number of factories, n = number of robots; uses prefix sums for distance

Algorithm Walkthrough

  1. Sort robots and factories by their positions. Sorting ensures that closer robots are considered for closer factories first.
  2. Initialize a DP table dp[i][j] representing the minimum distance to assign the first i robots using the first j factories. Initialize dp[0][0] = 0 (no robots assigned, zero distance).
  3. Iterate over factories in sorted order. For each factory j, consider assigning k robots to it, where 0 <= k <= limit[j] and k <= i (the remaining number of robots to assign).
  4. Compute distance sums efficiently using prefix sums for robots' positions. The total distance for assigning k robots to a factory is the sum of |robot[i] - factory[j].position| for the chosen robots.
  5. Update DP state:

dp[i][j] = min(dp[i][j], dp[i-k][j-1] + distance_sum_for_k_robots) 6. The answer is dp[n][m] after filling the DP table, representing all robots assigned to all factories.

Why it works:

  • Sorting guarantees that we always consider the closest robots for each factory first, avoiding suboptimal assignments.
  • DP correctly combines subproblems of assigning subsets of robots to subsets of factories, maintaining the minimal total distance invariant.
  • Prefix sums allow distance sums to be computed in O(1) for any consecutive group of robots.

Python Solution

from typing import List
import sys

class Solution:
    def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
        robot.sort()
        factory.sort(key=lambda x: x[0])
        n, m = len(robot), len(factory)
        
        # dp[i][j] = min distance to assign first i robots to first j factories
        dp = [[sys.maxsize] * (m + 1) for _ in range(n + 1)]
        dp[0][0] = 0
        
        for j in range(1, m + 1):
            pos, limit = factory[j-1]
            dp[0][j] = 0  # zero robots assigned
            for i in range(1, n + 1):
                # Assign 0 robots to current factory
                dp[i][j] = dp[i][j-1]
                dist_sum = 0
                # Try assigning k robots to this factory
                for k in range(1, min(limit, i) + 1):
                    dist_sum += abs(robot[i - k] - pos)
                    dp[i][j] = min(dp[i][j], dp[i - k][j - 1] + dist_sum)
        return dp[n][m]

Explanation:

  • Robots and factories are sorted to simplify distance minimization.
  • dp[i][j] stores the minimal distance for assigning i robots to the first j factories.
  • For each factory, we try assigning k robots (up to its capacity) and update the DP using the previous state.
  • dist_sum accumulates the distances for the robots assigned to the current factory efficiently.

Go Solution

package main

import (
    "math"
    "sort"
)

func minimumTotalDistance(robot []int, factory [][]int) int64 {
    sort.Ints(robot)
    sort.Slice(factory, func(i, j int) bool { return factory[i][0] < factory[j][0] })
    
    n, m := len(robot), len(factory)
    dp := make([][]int64, n+1)
    for i := range dp {
        dp[i] = make([]int64, m+1)
        for j := range dp[i] {
            dp[i][j] = math.MaxInt64
        }
    }
    dp[0][0] = 0
    
    for j := 1; j <= m; j++ {
        pos, limit := factory[j-1][0], factory[j-1][1]
        dp[0][j] = 0
        for i := 1; i <= n; i++ {
            dp[i][j] = dp[i][j-1]
            var distSum int64 = 0
            for k := 1; k <= limit && k <= i; k++ {
                distSum += int64(abs(robot[i-k] - pos))
                if dp[i-k][j-1] != math.MaxInt64 {
                    dp[i][j] = min(dp[i][j], dp[i-k][j-1]+distSum)
                }
            }
        }
    }
    return dp[n][m]
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func min(a, b int64) int64 {
    if a < b {
        return a
    }
    return b
}

Go-specific notes:

  • Uses slices of int64 to handle large distance sums safely.
  • Sorting uses sort.Slice with a custom comparator for factories.
  • No special handling needed for empty slices as constraints guarantee at least one robot and one factory.

Worked Examples

Example 1:

Input: robot = [0,4,6], factory = [[2,2],[6,2]]

Step-by-step DP updates:

i (robots) j (factories) Assigned robots to factory j Distance sum dp[i][j]
1 1 1 robot (0) 2-0
2 1 2 robots (0,4) 2-0
3 2 1 robot (6) 6-6

Final output: 4

**Example 2