Minimum Amount of Time to Collect Garbage — Solution
Minimum Amount of Time to Collect Garbage solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Minimum Amount of Time to Collect Garbage is a medium coding problem on arrays, strings and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Houses along a street are numbered from 0. garbage[i] lists the garbage bags at house i: each character is 'M' (metal), 'P' (paper) or 'G' (glass), and picking up one bag takes 1 minute. Driving from house i - 1 to house i takes travel[i - 1] minutes.
There are three trucks, one per kind of garbage, and each truck may only pick up its own kind. Every truck starts at house 0 and drives the houses in order, but it does not have to visit houses beyond the last one that holds its kind. Only one truck is active at any moment — while one drives or collects, the other two wait.
Return the minimum total number of minutes needed to collect all the garbage.
Example 1
Input: garbage = ["MG","P","GP","M"], travel = [3,1,2]
Output: 20
Explanation: Collecting the 6 bags takes 6 minutes. The metal truck drives to house 3 (3 + 1 + 2 = 6 minutes); the paper and glass trucks stop at house 2 (4 minutes each). 6 + 6 + 4 + 4 = 20.
Example 2
Input: garbage = ["G","G","G"], travel = [5,5]
Output: 13
Explanation: Only the glass truck moves: 3 minutes of collecting plus 10 of driving.
Constraints
2 <= garbage.length <= 10^5garbage[i] consists of only the letters 'M', 'P' and 'G'1 <= garbage[i].length <= 10travel.length == garbage.length - 11 <= travel[i] <= 100
Hints for Minimum Amount of Time to Collect Garbage
Hint 1
The collecting time does not depend on the trucks at all: it is the total number of bags.
Hint 2
Each truck's driving time is the travel time from house 0 to the last house containing its kind.
Hint 3
Record the last index of each kind and use prefix sums of
travel.
How to solve Minimum Amount of Time to Collect Garbage
Split the total into collecting time (one minute per bag, whatever the trucks do) and driving time (each truck goes exactly as far as the last house holding its kind).
Approach
- Add up the lengths of all
garbage[i]— the collecting time. - For each kind
M,P,G, find the last house index that contains it (0 if none). - Build prefix sums of
travelsoprefix[i]is the time to drive from house 0 to housei. - Return the collecting time plus
prefix[last[M]] + prefix[last[P]] + prefix[last[G]].
Why it works
Every bag must be picked up by its own truck, costing one minute each, so the collecting time is fixed. A truck must reach the last house with its kind, and since it drives the houses in order it passes every house before it; it never needs to go further. Trucks never wait for each other in a way that costs extra, because the total is just the sum of each truck's own driving and collecting.
Complexity
- Time —
O(total characters + n) - Space —
O(n) for the prefix sums (O(1) if you accumulate on the fly)
Pitfalls
- A kind that never appears costs nothing: its truck stays at house 0.
travel[i - 1]is the time to reach housei, so the prefix is shifted by one.- A house may hold several bags of the same kind; each costs a minute.
Reference solution
Python
from typing import List
def garbageCollection(garbage: List[str], travel: List[int]) -> int:
total = 0
last = {"M": 0, "P": 0, "G": 0}
for i, g in enumerate(garbage):
total += len(g)
for ch in g:
last[ch] = i
prefix = [0]
for t in travel:
prefix.append(prefix[-1] + t)
return total + sum(prefix[last[k]] for k in "MPG")Java
public static int garbageCollection(String[] garbage, int[] travel) {
int total = 0, lastM = 0, lastP = 0, lastG = 0;
for (int i = 0; i < garbage.length; i++) {
String g = garbage[i];
total += g.length();
if (g.indexOf('M') >= 0) lastM = i;
if (g.indexOf('P') >= 0) lastP = i;
if (g.indexOf('G') >= 0) lastG = i;
}
int[] prefix = new int[garbage.length];
for (int j = 1; j < garbage.length; j++) prefix[j] = prefix[j - 1] + travel[j - 1];
return total + prefix[lastM] + prefix[lastP] + prefix[lastG];
}C++
int garbageCollection(vector<string>& garbage, vector<int>& travel) {
int n = garbage.size();
int total = 0, lastM = 0, lastP = 0, lastG = 0;
for (int i = 0; i < n; i++) {
const string& g = garbage[i];
total += g.size();
if (g.find('M') != string::npos) lastM = i;
if (g.find('P') != string::npos) lastP = i;
if (g.find('G') != string::npos) lastG = i;
}
vector<int> prefix(n, 0);
for (int j = 1; j < n; j++) prefix[j] = prefix[j - 1] + travel[j - 1];
return total + prefix[lastM] + prefix[lastP] + prefix[lastG];
}JavaScript
var garbageCollection = function(garbage, travel) {
var total = 0, lastM = 0, lastP = 0, lastG = 0;
for (var i = 0; i < garbage.length; i++) {
var g = garbage[i];
total += g.length;
if (g.indexOf("M") >= 0) lastM = i;
if (g.indexOf("P") >= 0) lastP = i;
if (g.indexOf("G") >= 0) lastG = i;
}
var prefix = [0];
for (var j = 0; j < travel.length; j++) prefix.push(prefix[j] + travel[j]);
return total + prefix[lastM] + prefix[lastP] + prefix[lastG];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.