Minimum Amount of Time to Collect Garbage

Medium
1239.

Minimum Amount of Time to Collect Garbage

Minimum Amount of Time to Collect Garbage is a medium coding problem on arrays, strings and prefix sum, asked in Amazon and Google interviews.

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^5
  • 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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} garbage
 * @param {number[]} travel
 * @return {number}
 */
var garbageCollection = function(garbage, travel) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 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

Hints for Minimum Amount of Time to Collect Garbage

  1. Hint 1

    The collecting time does not depend on the trucks at all: it is the total number of bags.

  2. Hint 2

    Each truck's driving time is the travel time from house 0 to the last house containing its kind.

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

  1. Add up the lengths of all garbage[i] — the collecting time.
  2. For each kind M, P, G, find the last house index that contains it (0 if none).
  3. Build prefix sums of travel so prefix[i] is the time to drive from house 0 to house i.
  4. 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 house i, 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.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings