Leetcode Daily Question 31/10/2024 - 2463. Minimum Total Distance Traveled

Problem Description:

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

from typing import List
class Solution:
  def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
    robot.sort()
    factory.sort()
    m = len(robot)
    n = len(factory)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    for i in range(m):
      dp[i][n] = float('inf')
    
    for j in range(n - 1, -1, -1):
      prefix = 0
      queue = deque([(m,0)])
      for k in range(m - 1, -1, -1):
        prefix += abs(robot[k] - factory[j][0])
        if queue[0][0] > k + factory[j][1]:
          queue.popleft()
        while queue and queue[-1][1] >= dp[k][j+1] - prefix:
          queue.pop()
        queue.append((k, dp[k][j+1] - prefix))
        dp[k][j] = queue[0][1] + prefix
    
    return dp[0][0]

Explanation:

The goal is to find the optimal way to assign each robot to the nearest available factory, minimising the total distance using dp.

We use a dp table where dp[i][j] represents the minimum cumulative distance if we assign factories from factory[j:] to repair robots starting from robot[i:].

If we run out of factories before robots, we set dp[i][j] = float('inf') to mark that configuration as invalid.

We consider each possible assignment of robots to factories up to the factory’s limit. This allows us to check all feasible combinations that might give the lowest distance.

Using a deque, we keep track of the minimum distances in dp for valid assignments. This helps prune configurations that don’t improve the result, reducing unnecessary calculations and enhancing efficiency. We also pre-sort robot and factory to make the calculation linear.

def minimumTotalDistance(self, robot: List[int], factory: List[List[int]]) -> int:
    robot.sort()
    factory.sort()
    m = len(robot)
    n = len(factory)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    for i in range(m):
      dp[i][n] = float('inf')
    
    for j in range(n - 1, -1, -1):
      prefix = 0
      queue = deque([(m,0)])
      for k in range(m - 1, -1, -1):
        prefix += abs(robot[k] - factory[j][0])
        if queue[0][0] > k + factory[j][1]:
          queue.popleft()
        while queue and queue[-1][1] >= dp[k][j+1] - prefix:
          queue.pop()
        queue.append((k, dp[k][j+1] - prefix))
        dp[k][j] = queue[0][1] + prefix
    
    return dp[0][0]

The time complexity is O(m⋅n). Since we need to attempt every combination of factory and robot assignment.

The space complexity is O(m⋅n). Since we need to store information of each possible combination during dp.

The full solution can be found near the top of the page.