#2391

Medium

LeetCode Problem Workspace

Minimum Amount of Time to Collect Garbage

This problem asks you to find the minimum amount of time needed to collect all garbage in a city, focusing on array and string manipulation.

array string prefix sum

Problem Statement

You are given two arrays: 'garbage' and 'travel'. The 'garbage' array represents the garbage at each house, where each string contains 'M' (metal), 'P' (paper), and 'G' (glass). Picking up one unit of any type of garbage takes 1 minute. The 'travel' array represents the time required to travel between consecutive houses. The task is to compute the minimum time required to collect all the garbage.

You have three trucks, each responsible for collecting one type of garbage: metal, paper, and glass. Each truck starts at house 0 and travels to collect the corresponding garbage at each house. However, the trucks do not need to visit every house unless it contains their type of garbage. You need to find the optimal total time for all trucks to collect their respective garbage.

Examples

Example 1

Input: garbage = ["G","P","GP","GG"], travel = [2,4,3]

Output: 21

The paper garbage truck:

Travels from house 0 to house 1
Collects the paper garbage at house 1
Travels from house 1 to house 2
Collects the paper garbage at house 2 Altogether, it takes 8 minutes to pick up all the paper garbage. The glass garbage truck:
Collects the glass garbage at house 0
Travels from house 0 to house 1
Travels from house 1 to house 2
Collects the glass garbage at house 2
Travels from house 2 to house 3
Collects the glass garbage at house 3 Altogether, it takes 13 minutes to pick up all the glass garbage. Since there is no metal garbage, we do not need to consider the metal garbage truck. Therefore, it takes a total of 8 + 13 = 21 minutes to collect all the garbage.

Example 2

Input: garbage = ["MMM","PGM","GP"], travel = [3,10]

Output: 37

The metal garbage truck takes 7 minutes to pick up all the metal garbage. The paper garbage truck takes 15 minutes to pick up all the paper garbage. The glass garbage truck takes 15 minutes to pick up all the glass garbage. It takes a total of 7 + 15 + 15 = 37 minutes to collect all the garbage.

Constraints

2 <= garbage.length <= 105
garbage[i] consists of only the letters 'M', 'P', and 'G'.
1 <= garbage[i].length <= 10
travel.length == garbage.length - 1
1 <= travel[i] <= 100

Solution Approach

Identify the Last Collection Point

For each garbage type ('M', 'P', 'G'), find the last house where it is collected. This is important because trucks do not need to travel beyond the last occurrence of their respective garbage.

Calculate Travel Time

Once you know the last collection point for each truck, calculate the travel time by summing the travel array values up to that house. This ensures each truck travels only as far as needed to collect its garbage.

Sum Garbage Collection Time

Sum the times for each truck to pick up all its garbage (one minute per item) and add the travel times calculated in the previous step to get the total time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on iterating through the garbage and travel arrays, leading to a time complexity of O(n), where n is the number of houses. The space complexity is O(1) as we only need a few variables to track the last collection points and sum the travel times.

What Interviewers Usually Probe

Can the candidate efficiently identify the last collection points for each truck?
Does the candidate use the travel array effectively to minimize unnecessary trips?
Is the candidate able to break down the problem into smaller subproblems (garbage collection and travel time calculation)?

Common Pitfalls or Variants

Common pitfalls

Not considering the optimization where each truck only travels to the last house that has its garbage.
Overcomplicating the calculation by including unnecessary travel or not summing the garbage collection times correctly.
Failing to handle cases where one or more types of garbage are not present, which would affect the total time.

Follow-up variants

What if there are more than three types of garbage? This requires extending the approach to handle multiple garbage types.
How would the solution change if travel times were not provided in advance? This would require a dynamic approach for calculating travel times.
What if the garbage is arranged in a circular route? This would change how we calculate the travel times between houses.

FAQ

What is the key pattern to solve the Minimum Amount of Time to Collect Garbage problem?

The key pattern is array traversal combined with string manipulation, where you minimize travel time by stopping at the last house that has each type of garbage.

How do I avoid unnecessary travel in this problem?

By identifying the last house that contains each type of garbage, you ensure the trucks only travel as far as necessary.

What should I do if there are no garbage items for one of the types?

If a truck has no garbage to collect, it doesn't contribute to the total time. Simply skip it in the calculations.

How does the travel array influence the solution?

The travel array determines the time it takes to move between houses, and it's used to calculate the total time each truck spends collecting garbage.

What is the time complexity of this solution?

The time complexity is O(n), where n is the number of houses, since we iterate through the arrays to find the last collection points and sum the times.

terminal

Solution

Solution 1: Hash Table + Prefix Sum

According to the problem description, each garbage truck starts from house $0$, collects one type of garbage, and moves forward in order until it reaches the house index where this type of garbage last appears.

class Solution:
    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:
        last = {}
        ans = 0
        for i, s in enumerate(garbage):
            ans += len(s)
            for c in s:
                last[c] = i
        ts = 0
        for i, t in enumerate(travel, 1):
            ts += t
            ans += sum(ts for j in last.values() if i == j)
        return ans

Continue Practicing

#2381 shifting letters ii #2559 count vowel strings in ranges #2055 plates between candles