Problem Description

You have three types of garbage to collect: Metal ('M'), Paper ('P'), and Glass ('G'). These are distributed across different houses in a city.

Given:

• garbage[i]: A string representing the garbage at house i. Each character in the string is one unit of garbage ('M', 'P', or 'G')
• travel[i]: Time in minutes needed to travel from house i to house i + 1

You have three garbage trucks, one for each type of garbage. The rules are:

1. All trucks start at house 0
2. Each truck collects only its designated type of garbage
3. Trucks must visit houses in order (can't skip ahead and come back)
4. Trucks don't need to visit every house (can stop once they've collected all their garbage type)
5. Only one truck can operate at a time (while one is driving or collecting, others must wait)
6. Collecting one unit of garbage takes 1 minute

The goal is to find the minimum total time needed to collect all garbage.

For example, if house 2 has "MPG" and house 4 has "M", the Metal truck needs to:

• Travel from house 0 → 1 → 2 (collect 'M') → 3 → 4 (collect 'M')
• The Paper truck only needs to go to house 2
• The Glass truck only needs to go to house 2

The total time includes:

• Time to collect each unit of garbage (1 minute per unit)
• Travel time for each truck to reach the last house where its garbage type appears

Intuition

The key insight is that each garbage truck only needs to travel as far as the last house containing its type of garbage. Since trucks must visit houses in order and only one truck operates at a time, we don't need to worry about scheduling conflicts.

Think about it this way: if the last 'M' garbage is at house 3, the Metal truck must go through houses 0 → 1 → 2 → 3, regardless of whether those intermediate houses have Metal garbage or not. The truck will pick up any Metal garbage it finds along the way.

This means the total time consists of two parts:

1. Collection time: Every piece of garbage takes 1 minute to collect. This is simply the total number of garbage units across all houses.
2. Travel time: Each truck travels only up to its last required house.

For the travel time calculation, if the last occurrence of garbage type 'X' is at house j, the truck needs to travel through segments: travel[0] + travel[1] + ... + travel[j-1]. This is the sum of travel times from house 0 to house j.

The clever part is recognizing that we can track the last occurrence index for each garbage type while iterating through the houses. Then, we can calculate the travel distance needed for each truck by using prefix sums of the travel array. As we build the prefix sum, we can check if we've reached any truck's final destination and add that truck's travel time to our answer.

Since only one truck operates at a time, we simply add all individual truck times together - there's no overlap or optimization needed for scheduling.

Learn more about Prefix Sum patterns.

Solution Approach

The solution uses a hash table combined with prefix sum to efficiently calculate the minimum time needed.

Step 1: Track Last Occurrences and Count Garbage

We create a hash table last to store the last house index where each type of garbage appears. As we iterate through each house:

• Add the length of the garbage string at house i to our answer (this counts all garbage collection time)
• For each character c in the garbage string, update last[c] = i to track the latest occurrence

Step 2: Calculate Travel Times Using Prefix Sum

Instead of calculating the full prefix sum array upfront, we build it incrementally. We maintain a running sum ts of travel times:

• Start iterating through the travel array with index i starting from 1
• Add the current travel time to our running sum: ts += travel[i-1]
• At each position i, ts represents the total travel time from house 0 to house i

Step 3: Add Travel Times for Each Truck

The key optimization is checking if any truck's final destination is at the current house i:

• For each garbage type in last, if its last occurrence equals i, add the current prefix sum ts to the answer
• This means the truck for that garbage type needs to travel exactly ts minutes to reach its final destination

Example Walkthrough:

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

1. First pass: Count all garbage (7 units = 7 minutes) and find last = {'G': 3, 'P': 2}
2. Build prefix sum and check destinations:
   • At house 1: ts = 2, no truck stops here
   • At house 2: ts = 6, Paper truck stops here (add 6 minutes)
   • At house 3: ts = 9, Glass truck stops here (add 9 minutes)
3. Total: 7 (collection) + 6 (Paper travel) + 9 (Glass travel) = 22 minutes

This approach is efficient with O(n) time complexity, where n is the number of houses, as we only iterate through the arrays once.

Example Walkthrough

Let's walk through a concrete example with garbage = ["MMG", "PG", "M"] and travel = [3, 2].

Step 1: Count garbage and find last occurrences

Iterate through each house:

• House 0: "MMG" → 3 units of garbage (3 minutes collection time)
  • Update: last['M'] = 0, last['G'] = 0
• House 1: "PG" → 2 units of garbage (2 minutes collection time)
  • Update: last['P'] = 1, last['G'] = 1
• House 2: "M" → 1 unit of garbage (1 minute collection time)
  • Update: last['M'] = 2

Total collection time: 3 + 2 + 1 = 6 minutes Final last = {'M': 2, 'G': 1, 'P': 1}

Step 2: Calculate travel times using prefix sum

Build prefix sum while checking if any truck reaches its destination:

• At house 1:

  • Running travel sum: ts = 0 + 3 = 3 (travel from house 0→1)
  • Check destinations: Paper truck's last stop is house 1 (add 3 minutes)
  • Check destinations: Glass truck's last stop is house 1 (add 3 minutes)

• At house 2:

  • Running travel sum: ts = 3 + 2 = 5 (travel from house 0→1→2)
  • Check destinations: Metal truck's last stop is house 2 (add 5 minutes)

Step 3: Calculate total time

• Collection time: 6 minutes (all garbage units)
• Paper truck travel: 3 minutes (to house 1)
• Glass truck travel: 3 minutes (to house 1)
• Metal truck travel: 5 minutes (to house 2)

Total: 6 + 3 + 3 + 5 = 17 minutes

The efficiency comes from calculating each truck's travel distance only once using the running prefix sum, rather than recalculating paths for each truck separately.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × m), where n is the length of the garbage array and m is the average length of each garbage string. This is because:

• The first loop iterates through all garbage strings (n iterations) and for each string, iterates through all its characters (average m characters), resulting in O(n × m) operations
• The second loop iterates through the travel array (n-1 iterations) and for each iteration, checks at most k values in the last dictionary where k = 3 (types of garbage), resulting in O(n × k) = O(n) operations
• Overall time complexity: O(n × m) + O(n) = O(n × m)

The space complexity is O(k), where k is the number of garbage types. In this problem, k = 3 (for 'M', 'P', and 'G'). The space is used for:

• The last dictionary which stores at most k key-value pairs
• The variable ts and other constant space variables
• Overall space complexity: O(k) = O(3) = O(1)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient Nested Loop in Travel Time Calculation

The current implementation has a subtle inefficiency: for each house position, it checks ALL garbage types to see if any truck stops there. This creates an unnecessary nested loop structure.

Current problematic code:

for current_house, travel_time in enumerate(travel, start=1):
    cumulative_travel_time += travel_time
  
    # This inner loop runs for every house position!
    for last_house in last_house_for_type.values():
        if current_house == last_house:
            total_time += cumulative_travel_time

Why it's a problem:

• Even though there are only 3 garbage types (constant), this pattern doesn't scale well conceptually
• It performs unnecessary comparisons at each house position
• Makes the code harder to understand - why check all types at every position?

Better solution:

class Solution:
    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:
        last_house_for_type = {}
        total_time = 0
      
        # Count garbage and find last occurrences
        for house_index, garbage_at_house in enumerate(garbage):
            total_time += len(garbage_at_house)
            for garbage_type in garbage_at_house:
                last_house_for_type[garbage_type] = house_index
      
        # Calculate travel time for each truck directly
        for garbage_type, last_house in last_house_for_type.items():
            # Each truck travels from house 0 to its last required house
            total_time += sum(travel[:last_house])
      
        return total_time

2. Misunderstanding the Travel Array Indexing

A common mistake is misaligning the travel array indices with house positions.

Incorrect assumption: travel[i] is the time to reach house i Correct understanding: travel[i] is the time to go FROM house i TO house i+1

Example of wrong implementation:

# WRONG: This would incorrectly calculate travel times
for garbage_type, last_house in last_house_for_type.items():
    if last_house > 0:
        total_time += sum(travel[:last_house+1])  # Off by one!

Correct implementation:

# CORRECT: travel[:last_house] gives the sum of travel times to reach last_house
for garbage_type, last_house in last_house_for_type.items():
    if last_house > 0:
        total_time += sum(travel[:last_house])

3. Not Handling Edge Cases

Missing edge case checks:

• What if a garbage type doesn't exist at all?
• What if all garbage is at house 0?

Robust solution with edge case handling:

class Solution:
    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:
        if not garbage:
            return 0
          
        last_house_for_type = {}
        total_time = 0
      
        for house_index, garbage_at_house in enumerate(garbage):
            total_time += len(garbage_at_house)
            for garbage_type in garbage_at_house:
                last_house_for_type[garbage_type] = house_index
      
        # Only calculate travel time if trucks need to move past house 0
        for last_house in last_house_for_type.values():
            if last_house > 0:
                total_time += sum(travel[:last_house])
      
        return total_time

This approach is cleaner, more intuitive, and avoids the nested loop pattern while properly handling edge cases.