LeetCode 2391 - Minimum Amount of Time to Collect Garbage

This problem models a garbage collection system with three separate garbage trucks: - One truck collects metal garbage, represented by 'M' - One truck collects paper garbage, represented by 'P' - One truck collects glass garbage, represented by 'G' The input array garbage…

leetcodemediumarraystringprefix-sum

LeetCode Problem 2391

Difficulty: 🟡 Medium
Topics: Array, String, Prefix Sum

Solution

Problem Understanding

This problem models a garbage collection system with three separate garbage trucks:

  • One truck collects metal garbage, represented by 'M'
  • One truck collects paper garbage, represented by 'P'
  • One truck collects glass garbage, represented by 'G'

The input array garbage describes the garbage present at each house. For example, if garbage[i] = "GMP", then house i contains one unit each of glass, metal, and paper garbage.

Each unit of garbage takes exactly 1 minute to collect.

The travel array describes the travel time between adjacent houses. Specifically:

  • travel[i] is the time needed to move from house i to house i + 1

All three trucks start at house 0. A truck only needs to travel as far as the last house containing its garbage type. For example, if there is no paper garbage after house 4, then the paper truck never needs to go beyond house 4.

An important detail is that only one truck can operate at any given moment. However, this restriction does not actually complicate the computation because the trucks never overlap in time. The total answer is simply the sum of:

  • All garbage pickup times
  • All necessary travel times for each truck

The constraints are large:

  • Up to 10^5 houses
  • Each house string length is at most 10

This tells us the solution must be close to linear time. Any quadratic simulation would be too slow.

Several edge cases are important:

  • A garbage type may not appear at all
  • A garbage type may appear only at house 0, meaning no travel is needed
  • Multiple garbage types may share the same houses
  • Travel times can become large when summed repeatedly

The problem guarantees valid input sizes and valid garbage characters, so we do not need defensive validation logic.

Approaches

Brute Force Approach

A straightforward approach is to process each garbage type independently.

For each truck:

  1. Scan all houses to find every location containing that garbage type
  2. For every relevant house:
  • Add the pickup time
  • Recompute travel time from house 0 to that house

For example, if the glass truck needs to visit house 5, we could sum:

travel[0] + travel[1] + ... + travel[4]

every time we encounter a glass house.

This approach is correct because each truck independently contributes its pickup and travel costs. However, repeatedly recomputing travel prefixes is inefficient.

If there are n houses, repeatedly summing travel distances can lead to O(n^2) complexity in the worst case.

With n = 10^5, this would be too slow.

Optimal Approach

The key observation is that each truck only needs to travel to the last house containing its garbage type.

For example:

  • If the last metal garbage is at house 7, the metal truck only needs travel time from house 0 to house 7
  • It does not matter how many intermediate houses contain metal garbage, because the truck naturally passes through them

This leads to two important optimizations:

  1. Count all garbage units directly, since each unit costs exactly 1 minute
  2. Precompute prefix sums of travel times so we can instantly determine travel cost to any house

Using prefix sums:

prefix[i] = total travel time from house 0 to house i

Then:

  • Travel cost to house i becomes prefix[i]
  • We only add this once per garbage type, using the last occurrence

This reduces the entire solution to linear time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Repeatedly recomputes travel distances
Optimal O(n) O(n) Uses prefix sums and tracks last occurrence

Algorithm Walkthrough

  1. Initialize a variable total_time to store the final answer.
  2. Count all garbage pickup times by iterating through every house string and adding its length to total_time.

This works because every garbage character represents one unit that requires exactly one minute to collect. 3. Build a prefix sum array for travel times.

Let:

prefix[i] = total travel time from house 0 to house i

Since house 0 requires no travel:

prefix[0] = 0

Then:

prefix[i] = prefix[i - 1] + travel[i - 1]
  1. Track the last occurrence of each garbage type.

Create variables:

last_m
last_p
last_g

Initialize them to 0. 5. Scan through every house.

For each house:

  • If 'M' appears, update last_m
  • If 'P' appears, update last_p
  • If 'G' appears, update last_g

After the scan, each variable stores the furthest house that truck must visit. 6. Add the necessary travel costs.

Since prefix[i] represents travel cost from house 0 to house i:

total_time += prefix[last_m]
total_time += prefix[last_p]
total_time += prefix[last_g]
  1. Return total_time.

Why it works

The algorithm works because each truck only needs to travel to the furthest house containing its garbage type. Any garbage at earlier houses is automatically collected along the way.

The pickup time is simply the total number of garbage units, because each unit always costs one minute.

The prefix sum array guarantees that travel time to any house is computed correctly and efficiently in constant time.

Together, these properties ensure the algorithm computes the exact minimum total time.

Python Solution

from typing import List

class Solution:
    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:
        n = len(garbage)

        # Total pickup time
        total_time = sum(len(house) for house in garbage)

        # Prefix travel times
        prefix = [0] * n

        for i in range(1, n):
            prefix[i] = prefix[i - 1] + travel[i - 1]

        # Last occurrence of each garbage type
        last_m = 0
        last_p = 0
        last_g = 0

        for i, house in enumerate(garbage):
            if 'M' in house:
                last_m = i

            if 'P' in house:
                last_p = i

            if 'G' in house:
                last_g = i

        # Add travel costs
        total_time += prefix[last_m]
        total_time += prefix[last_p]
        total_time += prefix[last_g]

        return total_time

The implementation follows the algorithm directly.

First, the code computes the pickup time using:

sum(len(house) for house in garbage)

This counts every garbage unit exactly once.

Next, the prefix sum array is constructed. The value at prefix[i] stores the total travel time needed to reach house i from house 0.

The algorithm then scans all houses and records the last position where each garbage type appears. Membership checks such as:

'M' in house

work efficiently because each house string length is at most 10.

Finally, the travel costs for the three trucks are added using the prefix sums.

The solution runs in linear time and satisfies the problem constraints comfortably.

Go Solution

func garbageCollection(garbage []string, travel []int) int {
	n := len(garbage)

	// Total pickup time
	totalTime := 0
	for _, house := range garbage {
		totalTime += len(house)
	}

	// Prefix travel times
	prefix := make([]int, n)

	for i := 1; i < n; i++ {
		prefix[i] = prefix[i-1] + travel[i-1]
	}

	// Last occurrence of each garbage type
	lastM, lastP, lastG := 0, 0, 0

	for i, house := range garbage {
		for _, ch := range house {
			if ch == 'M' {
				lastM = i
			} else if ch == 'P' {
				lastP = i
			} else if ch == 'G' {
				lastG = i
			}
		}
	}

	// Add travel costs
	totalTime += prefix[lastM]
	totalTime += prefix[lastP]
	totalTime += prefix[lastG]

	return totalTime
}

The Go implementation mirrors the Python solution closely.

Instead of using substring membership checks like Python, the Go version iterates through each character in the house string using a for range loop.

All calculations safely fit inside Go's int type because the maximum possible answer is well within integer limits.

Slices are used naturally for both the travel array and the prefix sum array.

Worked Examples

Example 1

Input:

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

Step 1: Count Pickup Time

House Garbage Length
0 "G" 1
1 "P" 1
2 "GP" 2
3 "GG" 2

Total pickup time:

1 + 1 + 2 + 2 = 6

Step 2: Build Prefix Sum

House Prefix Travel
0 0
1 2
2 6
3 9

Step 3: Find Last Occurrences

Garbage Type Last House
M 0
P 2
G 3

Step 4: Add Travel Costs

Metal:  prefix[0] = 0
Paper:  prefix[2] = 6
Glass:  prefix[3] = 9

Total travel:

0 + 6 + 9 = 15

Final Answer

Pickup time + travel time
= 6 + 15
= 21

Example 2

Input:

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

Step 1: Count Pickup Time

House Garbage Length
0 "MMM" 3
1 "PGM" 3
2 "GP" 2

Total pickup:

3 + 3 + 2 = 8

Step 2: Build Prefix Sum

House Prefix Travel
0 0
1 3
2 13

Step 3: Last Occurrences

Garbage Type Last House
M 1
P 2
G 2

Step 4: Add Travel Costs

Metal:  prefix[1] = 3
Paper:  prefix[2] = 13
Glass:  prefix[2] = 13

Total travel:

3 + 13 + 13 = 29

Final Answer

Pickup + travel
= 8 + 29
= 37

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each house and travel entry is processed a constant number of times
Space O(n) The prefix sum array stores one value per house

The algorithm performs a few linear scans across the input arrays. No nested iteration over houses occurs, so the runtime grows proportionally with the number of houses.

The additional memory comes from the prefix sum array. Aside from that, only a few integer variables are used.

Test Cases

from typing import List

class Solution:
    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:
        n = len(garbage)

        total_time = sum(len(house) for house in garbage)

        prefix = [0] * n

        for i in range(1, n):
            prefix[i] = prefix[i - 1] + travel[i - 1]

        last_m = 0
        last_p = 0
        last_g = 0

        for i, house in enumerate(garbage):
            if 'M' in house:
                last_m = i

            if 'P' in house:
                last_p = i

            if 'G' in house:
                last_g = i

        total_time += prefix[last_m]
        total_time += prefix[last_p]
        total_time += prefix[last_g]

        return total_time

solution = Solution()

# Example 1
assert solution.garbageCollection(
    ["G", "P", "GP", "GG"],
    [2, 4, 3]
) == 21  # Standard mixed garbage example

# Example 2
assert solution.garbageCollection(
    ["MMM", "PGM", "GP"],
    [3, 10]
) == 37  # All truck types travel

# Only one house
assert solution.garbageCollection(
    ["MPG"],
    []
) == 3  # No travel required

# Only metal garbage exists
assert solution.garbageCollection(
    ["M", "M", "M"],
    [1, 1]
) == 5  # One truck travels to last house

# Garbage only at first house
assert solution.garbageCollection(
    ["GMP", "", ""],
    [5, 5]
) == 3  # No truck needs travel

# Long travel but little garbage
assert solution.garbageCollection(
    ["G", "", "", "", "P"],
    [10, 10, 10, 10]
) == 42  # Large travel accumulation

# Multiple garbage types at same house
assert solution.garbageCollection(
    ["MPG", "MPG", "MPG"],
    [2, 2]
) == 21  # All trucks travel together logically

# Sparse garbage distribution
assert solution.garbageCollection(
    ["M", "", "P", "", "G"],
    [1, 2, 3, 4]
) == 23  # Different last positions

print("All tests passed!")
Test Why
["G","P","GP","GG"] Verifies standard mixed input
["MMM","PGM","GP"] Verifies all trucks travel independently
["MPG"] Tests minimum house count with no travel
["M","M","M"] Tests single garbage type
["GMP","",""] Tests garbage only at starting house
["G","","","","P"] Tests large travel accumulation
["MPG","MPG","MPG"] Tests all trucks sharing same route
["M","","P","","G"] Tests sparse last occurrences

Edge Cases

One important edge case occurs when a garbage type never appears at all. For example, there may be no metal garbage anywhere in the city. A buggy implementation might still add travel time for the metal truck unnecessarily. This solution avoids that issue naturally because the last occurrence remains at house 0, and prefix[0] equals 0.

Another important case is when all garbage exists only at house 0. In this situation, no truck should travel anywhere. The implementation handles this correctly because all last occurrence indices remain 0, so no travel cost is added.

A third important edge case is sparse garbage placement. For example, metal garbage may appear at house 1, paper at house 50, and glass at house 99. A naive implementation might repeatedly recompute travel paths or accidentally double count distances. The prefix sum structure ensures every required travel distance is computed exactly once in constant time.

A final subtle edge case involves empty house strings. Some houses may contain no garbage at all. The algorithm still processes them correctly because empty strings contribute zero pickup time and do not affect last occurrence tracking.