Minimum Amount of Time to Collect Garbage - Solution & Explanation

Q: Is Minimum Amount of Time to Collect Garbage easy or hard?

LeetCode classifies the problem as Medium. The logic is straightforward once you realize each truck only travels to its last required house, but identifying this optimization and applying prefix sums requires intermediate array reasoning.

Q: Minimum Amount of Time to Collect Garbage Python/Java solution

The implementation in Python or Java follows the same logic: iterate through the garbage array, count characters for pickup time, record the last position of each garbage type, and use prefix sums of the travel array to compute travel cost efficiently.

Q: How to solve Minimum Amount of Time to Collect Garbage in O(n)?

Iterate through the houses and count each garbage piece since pickup takes one minute per item. Track the last index where M, P, and G appear. Build a prefix sum of travel times so the cost to reach any house is constant time. Add pickup time plus the travel cost to the last house for each truck.

Q: What is the best approach for Minimum Amount of Time to Collect Garbage?

The optimal approach uses prefix sums to compute cumulative travel time and tracks the last occurrence of each garbage type (M, P, G). The algorithm scans the houses once, counts pickup time, and adds travel time only up to the last relevant house for each truck. This results in O(n) time complexity.

Q: Is Minimum Amount of Time to Collect Garbage asked at Google/Amazon/Meta?

Array and prefix sum problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The question tests ability to track last occurrences, handle cumulative costs, and reason about independent processes.

Q: What data structure is used in Minimum Amount of Time to Collect Garbage?

The solution mainly uses arrays and prefix sums. Arrays store garbage strings and travel times, while a prefix sum array allows constant-time calculation of travel distance to any house index.

Q: What is the time complexity of Minimum Amount of Time to Collect Garbage?

The optimal solution runs in O(n) time where n is the number of houses. Each house is scanned once to count garbage pieces and record the last occurrence of each type. Prefix sum preprocessing for travel also takes O(n).

MediumArray String Prefix Sum24 min readAsked at: Microsoft, Google

Practice this problem

Problem Statement

You are given a 0-indexed array of strings garbage where garbage[i] represents the assortment of garbage at the i^th house. garbage[i] consists only of the characters 'M', 'P' and 'G' representing one unit of metal, paper and glass garbage respectively. Picking up one unit of any type of garbage takes 1 minute.

You are also given a 0-indexed integer array travel where travel[i] is the number of minutes needed to go from house i to house i + 1.

There are three garbage trucks in the city, each responsible for picking up one type of garbage. Each garbage truck starts at house 0 and must visit each house in order; however, they do not need to visit every house.

Only one garbage truck may be used at any given moment. While one truck is driving or picking up garbage, the other two trucks cannot do anything.

Return the minimum number of minutes needed to pick up all the garbage.

Example 1:

Input: garbage = ["G","P","GP","GG"], travel = [2,4,3]
Output: 21
Explanation:
The paper garbage truck:
1. Travels from house 0 to house 1
2. Collects the paper garbage at house 1
3. Travels from house 1 to house 2
4. Collects the paper garbage at house 2
Altogether, it takes 8 minutes to pick up all the paper garbage.
The glass garbage truck:
1. Collects the glass garbage at house 0
2. Travels from house 0 to house 1
3. Travels from house 1 to house 2
4. Collects the glass garbage at house 2
5. Travels from house 2 to house 3
6. 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
Explanation:
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 <= 10⁵
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

Approach Overview

Problem Overview: You are given an array garbage where each string represents garbage types at a house (M, P, G) and a travel array representing time between houses. Three trucks collect metal, paper, and glass separately. The goal is to compute the minimum total time needed for all trucks to collect their respective garbage.

Approach 1: Separate Calculation for Each Truck Type (O(n) time, O(1) space)

This approach treats each garbage truck independently. First count the total number of garbage pieces across all houses because picking up each piece costs one minute. Then determine the last house that contains each garbage type (M, P, G). Each truck only needs to travel up to the last house where its garbage appears. Sum the travel times up to those indices and add them to the pickup time. The method relies on simple iteration over the array of houses and works well because the trucks operate independently.

Approach 2: Prefix Sum Method for Optimized Travel Calculation (O(n) time, O(n) space)

This method precomputes a prefix sum of the travel array so the travel cost between house 0 and any house i can be retrieved in constant time. While iterating through the houses, track the latest position of each garbage type. After the scan, use the prefix sum to quickly compute how far each truck must travel. The total time becomes the number of garbage pieces plus the prefix travel cost for the last occurrence of M, P, and G. The prefix structure avoids repeatedly summing travel segments and is a common pattern when working with cumulative distances in prefix sum problems.

Both solutions rely on scanning the string representation of garbage at each house and counting characters to determine pickup time. The main optimization comes from realizing that trucks never need to travel beyond the last house containing their garbage type.

Recommended for interviews: The prefix sum approach is usually preferred because it demonstrates awareness of cumulative preprocessing and constant-time range cost calculation. However, starting with the direct per-truck calculation shows you understand the problem mechanics. Interviewers typically expect the O(n) solution with clear reasoning about last occurrences and travel accumulation.

Approach 1: Prefix Sum Method for Optimized Travel Calculation

The goal is to calculate the minimum time required for each truck to collect all the garbage of its type. A key observation is that the truck only needs to travel as far as the last house that has a specific kind of garbage. We use a prefix sum approach to calculate travel times efficiently. Each truck collects the garbage as it travels to each house that contains its type of garbage.

This C implementation first calculates the prefix sum of travel times. It then iterates through each house, updating the last index for each type of garbage (using the ASCII code for 'M', 'P', 'G' as keys). At the end, it calculates the total time by adding the travel time up to the last house containing each type of garbage.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n * m) where n is the number of houses and m is the average number of garbage types per house.
Space Complexity: O(1) aside from the input storage.

Try this approach in the editor →

Approach 2: Separate Calculation for Each Truck Type

Instead of combining the travel times, here we individually compute the travel needed for each garbage type truck. This method essentially iterates through the garbage list and sums up the necessary travel times and garbage pickup times separately for 'M', 'P', and 'G'. Once that's done, the total represents the minimum time required.

This C function 'getTime' separately processes each garbage type determined by the input 'type'. It iterates over the garbage list, increments time with the number of relevant garbage pieces, and accumulates travel time from the last recorded pickup location.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

Time Complexity: O(n * m) for each separate call, leading to overall O(3 * n * m).
Space Complexity: O(1) aside from input size.

Try this approach in the editor →

Approach 3: 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.

Therefore, we can use a hash table last to record the house index where each type of garbage last appears. We assume that the i-th type of garbage last appears in the j-th house, then the driving time required for the i-th truck is travel[0] + travel[1] + cdots + travel[j-1]. Note, if j = 0, no driving time is needed. We accumulate the driving time of all vehicles, add the total collection time of each type of garbage, and we can get the answer.

The time complexity is O(n), and the space complexity is O(k), where n and k are the number and types of garbage, respectively. In this problem, k = 3.

Code

Python Java C++Go TypeScript Rust C#

Python

Java

C++

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Prefix Sum Method for Optimized Travel Calculation	Time Complexity: O(n * m) where n is the number of houses and m is the average number of garbage types per house. Space Complexity: O(1) aside from the input storage.
Separate Calculation for Each Truck Type	Time Complexity: O(n * m) for each separate call, leading to overall O(3 * n * m). Space Complexity: O(1) aside from input size.
Hash Table + Prefix Sum	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Separate Calculation for Each Truck Type	O(n)	O(1)	When you want the simplest implementation and minimal memory usage
Prefix Sum Method for Travel Cost	O(n)	O(n)	When travel costs must be queried quickly for multiple indices

Video Solution

Minimum Amount of Time to Collect Garbage | Simple Clean | Leetcode-2391 • codestorywithMIK • 5,905 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Amount of Time to Collect Garbage easy or hard?

LeetCode classifies the problem as Medium. The logic is straightforward once you realize each truck only travels to its last required house, but identifying this optimization and applying prefix sums requires intermediate array reasoning.

Minimum Amount of Time to Collect Garbage Python/Java solution

The implementation in Python or Java follows the same logic: iterate through the garbage array, count characters for pickup time, record the last position of each garbage type, and use prefix sums of the travel array to compute travel cost efficiently.

How to solve Minimum Amount of Time to Collect Garbage in O(n)?

Iterate through the houses and count each garbage piece since pickup takes one minute per item. Track the last index where M, P, and G appear. Build a prefix sum of travel times so the cost to reach any house is constant time. Add pickup time plus the travel cost to the last house for each truck.

What is the best approach for Minimum Amount of Time to Collect Garbage?

The optimal approach uses prefix sums to compute cumulative travel time and tracks the last occurrence of each garbage type (M, P, G). The algorithm scans the houses once, counts pickup time, and adds travel time only up to the last relevant house for each truck. This results in O(n) time complexity.

Is Minimum Amount of Time to Collect Garbage asked at Google/Amazon/Meta?

Array and prefix sum problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The question tests ability to track last occurrences, handle cumulative costs, and reason about independent processes.

What data structure is used in Minimum Amount of Time to Collect Garbage?

The solution mainly uses arrays and prefix sums. Arrays store garbage strings and travel times, while a prefix sum array allows constant-time calculation of travel distance to any house index.

What is the time complexity of Minimum Amount of Time to Collect Garbage?

The optimal solution runs in O(n) time where n is the number of houses. Each house is scanned once to count garbage pieces and record the last occurrence of each type. Prefix sum preprocessing for travel also takes O(n).

Ready to solve this problem?

Practice Minimum Amount of Time to Collect Garbage with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyMedium

Acceptance85.2%

Approaches3

Reading time24 min

Asked at

Microsoft Google

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Prefix Sum Method for Optimized Travel Calculation

Code

Complexity

Approach 2: Separate Calculation for Each Truck Type

Code

Complexity

Approach 3: Hash Table + Prefix Sum

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents