Watch 10 video solutions for Minimum Amount of Time to Collect Garbage, a medium level problem involving Array, String, Prefix Sum. This walkthrough by codestorywithMIK has 5,572 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed array of strings garbage where garbage[i] represents the assortment of garbage at the ith 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 <= 105garbage[i] consists of only the letters 'M', 'P', and 'G'.1 <= garbage[i].length <= 10travel.length == garbage.length - 11 <= travel[i] <= 100Problem 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 | 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 |