3538. Merge Operations for Minimum Travel Time LeetCode Solution

Last updated: May 5, 2025

In this guide, you will get 3538. Merge Operations for Minimum Travel Time LeetCode Solution with the best time and space complexity. The solution to Merge Operations for Minimum Travel Time problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Merge Operations for Minimum Travel Time solution in C++
Merge Operations for Minimum Travel Time solution in Java
Merge Operations for Minimum Travel Time solution in Python
Additional Resources

3538. Merge Operations for Minimum Travel Time LeetCode Solution image

Problem Statement of Merge Operations for Minimum Travel Time

You are given a straight road of length l km, an integer n, an integer k, and two integer arrays, position and time, each of length n.
The array position lists the positions (in km) of signs in strictly increasing order (with position[0] = 0 and position[n – 1] = l).
Each time[i] represents the time (in minutes) required to travel 1 km between position[i] and position[i + 1].
You must perform exactly k merge operations. In one merge, you can choose any two adjacent signs at indices i and i + 1 (with i > 0 and i + 1 < n) and:

Update the sign at index i + 1 so that its time becomes time[i] + time[i + 1].
Remove the sign at index i.

Return the minimum total travel time (in minutes) to travel from 0 to l after exactly k merges.

Example 1:

Input: l = 10, n = 4, k = 1, position = [0,3,8,10], time = [5,8,3,6]
Output: 62
Explanation:

Merge the signs at indices 1 and 2. Remove the sign at index 1, and change the time at index 2 to 8 + 3 = 11.

After the merge:

position array: [0, 8, 10]
time array: [5, 11, 6]

Segment
Distance (km)
Time per km (min)
Segment Travel Time (min)

0 → 8
8
5
8 × 5 = 40

8 → 10
2
11
2 × 11 = 22

Total Travel Time: 40 + 22 = 62, which is the minimum possible time after exactly 1 merge.

Example 2:

Input: l = 5, n = 5, k = 1, position = [0,1,2,3,5], time = [8,3,9,3,3]
Output: 34
Explanation:

Merge the signs at indices 1 and 2. Remove the sign at index 1, and change the time at index 2 to 3 + 9 = 12.
After the merge:

position array: [0, 2, 3, 5]
time array: [8, 12, 3, 3]

Segment
Distance (km)
Time per km (min)
Segment Travel Time (min)

0 → 2
2
8
2 × 8 = 16

2 → 3
1
12
1 × 12 = 12

3 → 5
2
3
2 × 3 = 6

Total Travel Time: 16 + 12 + 6 = 34, which is the minimum possible time after exactly 1 merge.

Constraints:

1 <= l <= 105
2 <= n <= min(l + 1, 50)
0 <= k <= min(n – 2, 10)
position.length == n
position[0] = 0 and position[n – 1] = l
position is sorted in strictly increasing order.
time.length == n
1 <= time[i] <= 100
1 <= sum(time) <= 100

Complexity Analysis

Time Complexity: O(k^2n^2)
Space Complexity: O(kn^2)

3538. Merge Operations for Minimum Travel Time LeetCode Solution in C++

class Solution:
  def minTravelTime(
      self,
      l: int,
      n: int,
      k: int,
      position: list[int],
      time: list[int]
  ) -> int:
    prefix = list(itertools.accumulate(time))

    @functools.lru_cache(None)
    def dp(i: int, skips: int, last: int) -> int:
      """
      Returns the minimum travel time to reach the last stop from i-th stop,
      with `skips` skips remaining, and the last stop being `last`.
      """
      if i == n - 1:
        return 0 if skips == 0 else math.inf
      res = math.inf
      rate = prefix[i] - (prefix[last - 1] if last > 0 else 0)
      end = min(n - 1, i + skips + 1)
      for j in range(i + 1, end + 1):
        distance = position[j] - position[i]
        res = min(res, distance * rate + dp(j, skips - (j - i - 1), i + 1))
      return res

    return dp(0, k, 0)
/* code provided by PROGIEZ */

3538. Merge Operations for Minimum Travel Time LeetCode Solution in Java

N/A
// code provided by PROGIEZ

3538. Merge Operations for Minimum Travel Time LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents