Minimum Total Distance Traveled — LeetCode 2463 Python Solution
HardArrayDynamic ProgrammingSorting
- Problem
- #2463
- Pattern
- Sorting
- Reading time
- 4 min
- Source
- leetcode.com
The 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.
Example
- Input
- robot = [0,4,6], factory = [[2,2],[6,2]]
- Output
- 4
- Explanation
- As shown in the figure:
Python solution
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 ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(m^2 \times n) |
| Space | O(m \times n) auxiliary |
Pattern: Sorting
Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 2463. Minimum Total Distance Traveled is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.
The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2463. Minimum Total Distance Traveled?
- LeetCode 2463. Minimum Total Distance Traveled is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2463. Minimum Total Distance Traveled?
- The Python solution on this page runs in O(m^2 \times n).
- What is the space complexity of LeetCode 2463. Minimum Total Distance Traveled?
- The Python solution on this page uses O(m \times n) auxiliary space.
- What topics does LeetCode 2463. Minimum Total Distance Traveled cover?
- LeetCode 2463. Minimum Total Distance Traveled is tagged Array, Dynamic Programming and Sorting on LeetCode.