2391 Minimum Amount of Time to Collect Garbage Solution

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

The problem

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.

Python

def minTimeToCollectGarbage(garbage, travel):
    last = {c: 0 for c in 'MPG'}
    prefix_sum = [0] * (len(travel) + 1)
    
    for i in range(1, len(travel) + 1):
        prefix_sum[i] = prefix_sum[i - 1] + travel[i - 1]

    total_time = 0

    for i, g in enumerate(garbage):
        for char in g:
            total_time += 1
            last[char] = i

    for c in 'MPG':
        total_time += prefix_sum[last[c]]

    return total_time

garbage = ["G", "P", "GP", "GG"]
travel = [2, 4, 3]
print(minTimeToCollectGarbage(garbage, travel))  # Output: 21

Java

import java.util.List;

public class GarbageCollection {
    public int minTimeToCollectGarbage(List<String> garbage, List<Integer> travel) {
        int[] last = new int[256];
        int[] prefixSum = new int[travel.size() + 1];

        for (int i = 1; i <= travel.size(); i++) {
            prefixSum[i] = prefixSum[i - 1] + travel.get(i - 1);
        }

        int totalTime = 0;

        for (int i = 0; i < garbage.size(); i++) {
            for (char g : garbage.get(i).toCharArray()) {
                totalTime++;
                last[g] = i;
            }
        }

        for (char g : new char[]{'M', 'P', 'G'}) {
            totalTime += prefixSum[last[g]];
        }

        return totalTime;
    }

    public static void main(String[] args) {
        List<String> garbage = List.of("G", "P", "GP", "GG");
        List<Integer> travel = List.of(2, 4, 3);
        GarbageCollection gc = new GarbageCollection();
        System.out.println(gc.minTimeToCollectGarbage(garbage, travel)); // Output: 21
    }
}

C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int minTimeToCollectGarbage(vector<string>& garbage, vector<int>& travel) {
    vector<int> last(256, 0);
    vector<int> prefixSum(travel.size() + 1, 0);
    for (int i = 1; i <= travel.size(); ++i) {
        prefixSum[i] = prefixSum[i - 1] + travel[i - 1];
    }
    int total_time = 0;
    for (int i = 0; i < garbage.size(); ++i) {
        for (char g : garbage[i]) {
            total_time++;
            last[g] = i;
        }
    }
    for (char g : {'M', 'P', 'G'}) {
        total_time += prefixSum[last[g]];
    }
    return total_time;
}

int main() {
    vector<string> garbage = {"G", "P", "GP", "GG"};
    vector<int> travel = {2, 4, 3};
    cout << minTimeToCollectGarbage(garbage, travel) << endl; // Output: 21
    return 0;
}

JavaScript

function minTimeToCollectGarbage(garbage, travel) {
  const last = {'M': 0, 'P': 0, 'G': 0};
  const prefixSum = [0];
  
  for (let i = 0; i < travel.length; i++) {
    prefixSum[i + 1] = prefixSum[i] + travel[i];
  }

  let totalTime = 0;

  for (let i = 0; i < garbage.length; i++) {
    for (const char of garbage[i]) {
      totalTime++;
      if (i > last[char]) {
        last[char] = i;
      }
    }
  }

  for (const type of ['M', 'P', 'G']) {
    totalTime += prefixSum[last[type]];
  }
  
  return totalTime;
}

const garbage = ["G", "P", "GP", "GG"];
const travel = [2, 4, 3];
console.log(minTimeToCollectGarbage(garbage, travel)); // Output: 21

#include <stdio.h>
#include <string.h>

int minTimeToCollectGarbage(char** garbage, int garbageSize, int* travel, int travelSize){
    int time = 0;
    int last[256] = {0};
    int prefixSum[100001] = {0};

    for (int i = 1; i < garbageSize; i++) {
        prefixSum[i] = prefixSum[i - 1] + travel[i - 1];
    }

    for (int i = 0; i < garbageSize; i++) {
        for (int j = 0; garbage[i][j]; j++) {
            char g = garbage[i][j];
            time++;
            last[g] = i;
        }
    }

    for (int i = 0; i < 256; i++) {
        if (last[i]) {
            time += prefixSum[last[i]];
        }
    }

    return time;
}

int main() {
    char* garbage[] = {"G", "P", "GP", "GG"};
    int travel[] = {2, 4, 3};
    int result = minTimeToCollectGarbage(garbage, 4, travel, 3);
    printf("%d\n", result); // Output: 21
    return 0;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int MinTimeToCollectGarbage(IList<string> garbage, IList<int> travel) {
        int[] last = new int[256];
        int[] prefixSum = new int[travel.Count + 1];

        for (int i = 1; i <= travel.Count; ++i) {
            prefixSum[i] = prefixSum[i - 1] + travel[i - 1];
        }

        int totalTime = 0;

        for (int i = 0; i < garbage.Count; i++) {
            foreach (char g in garbage[i]) {
                totalTime++;
                last[g] = i;
            }
        }

        foreach (char g in "MPG") {
            totalTime += prefixSum[last[g]];
        }

        return totalTime;
    }

    public static void Main(string[] args) {
        var garbage = new List<string> { "G", "P", "GP", "GG" };
        var travel = new List<int> { 2, 4, 3 };
        Solution sol = new Solution();
        Console.WriteLine(sol.MinTimeToCollectGarbage(garbage, travel)); // Output: 21
    }
}

Python leverages a dictionary to store the last index of each garbage type for direct access. The prefix sum calculated via a list aids in accumulating travel times. The pattern of calculation runs similarly to other languages, focusing on simplicity and clarity.

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

Python

def get_time(garbage, travel, gtype):
    last = -1
    time = 0
    for i, house in enumerate(garbage):
        if gtype in house:
            time += house.count(gtype)
            if i != 0 and last != -1:
                time += travel[last]
            last = i - 1
    return time


def min_time_to_collect_garbage(garbage, travel):
    return (get_time(garbage, travel, 'M') +
            get_time(garbage, travel, 'P') +
            get_time(garbage, travel, 'G'))

garbage = ["MMM", "PGM", "GP"]
travel = [3, 10]
print(min_time_to_collect_garbage(garbage, travel))  # Output: 37

Java

import java.util.List;

public class GarbageCollectionSep {
    private int getTime(List<String> garbage, List<Integer> travel, char type) {
        int last = -1;
        int time = 0;

        for (int i = 0; i < garbage.size(); i++) {
            String house = garbage.get(i);
            for (char ch : house.toCharArray()) {
                if (ch == type) {
                    time++;
                }
            }
            if (house.indexOf(type) != -1) {
                if (i > 0 && last != -1) {
                    time += travel.get(last);
                }
                last = i - 1;
            }
        }
        return time;
    }

    public int minTimeToCollectGarbage(List<String> garbage, List<Integer> travel) {
        return getTime(garbage, travel, 'M') +
               getTime(garbage, travel, 'P') +
               getTime(garbage, travel, 'G');
    }

    public static void main(String[] args) {
        List<String> garbage = List.of("MMM", "PGM", "GP");
        List<Integer> travel = List.of(3, 10);
        GarbageCollectionSep gc = new GarbageCollectionSep();
        System.out.println(gc.minTimeToCollectGarbage(garbage, travel)); // Output: 37
    }
}

C++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int getTime(const vector<string>& garbage, const vector<int>& travel, char type) {
    int last = -1, time = 0;
    for (size_t i = 0; i < garbage.size(); ++i) {
        for (char ch : garbage[i]) {
            if (ch == type) {
                ++time;
            }
        }
        if (garbage[i].find(type) != string::npos) {
            if (i > 0 && last != -1) {
                time += travel[last];
            }
            last = i - 1;
        }
    }
    return time;
}

int minTimeToCollectGarbage(vector<string>& garbage, vector<int>& travel) {
    return getTime(garbage, travel, 'M') +
           getTime(garbage, travel, 'P') +
           getTime(garbage, travel, 'G');
}

int main() {
    vector<string> garbage = {"MMM", "PGM", "GP"};
    vector<int> travel = {3, 10};
    cout << minTimeToCollectGarbage(garbage, travel) << endl; // Output: 37
    return 0;
}

JavaScript

function getTime(garbage, travel, type) {
  let last = -1; 
  let time = 0;

  for (let i = 0; i < garbage.length; i++) {
    const house = garbage[i];
    for (let ch of house) {
      if (ch === type) {
        time++;
      }
    }
    if (house.includes(type)) {
      if (i > 0 && last !== -1) {
        time += travel[last];
      }
      last = i - 1;
    }
  }
  return time;
}

function minTimeToCollectGarbage(garbage, travel) {
  return getTime(garbage, travel, 'M') +
         getTime(garbage, travel, 'P') +
         getTime(garbage, travel, 'G');
}

const garbage = ["MMM", "PGM", "GP"];
const travel = [3, 10];
console.log(minTimeToCollectGarbage(garbage, travel)); // Output: 37

#include <stdio.h>
#include <string.h>

int getTime(char **garbage, int garbageSize, int *travel, int *last, char type) {
    int time = 0;
    for (int i = 0; i < garbageSize; i++) {
        if (strchr(garbage[i], type)) {
            for (int j = 0; garbage[i][j] != '\0'; j++) {
                if (garbage[i][j] == type) {
                    time++;
                }
            }
            if (i != 0) {
                time += travel[last[type]];
                last[type] = i;
            }
        }
    }
    return time;
}

int minTimeToCollectGarbage(char** garbage, int garbageSize, int* travel, int travelSize){
    int last[256] = {-1};
    int totalTime = getTime(garbage, garbageSize, travel, last, 'M') + 
                    getTime(garbage, garbageSize, travel, last, 'P') + 
                    getTime(garbage, garbageSize, travel, last, 'G');
    return totalTime;
}

int main() {
    char* garbage[] = {"MMM", "PGM", "GP"};
    int travel[] = {3, 10};
    int result = minTimeToCollectGarbage(garbage, 3, travel, 2);
    printf("%d\n", result); // Output: 37
    return 0;
}

using System;
using System.Collections.Generic;

public class SolutionSep {
    private int GetTime(List<string> garbage, List<int> travel, char type) {
        int last = -1;
        int time = 0;

        for (int i = 0; i < garbage.Count; i++) {
            string house = garbage[i];
            foreach (char ch in house) {
                if (ch == type) {
                    time++;
                }
            }
            if (house.Contains(type)) {
                if (i > 0 && last != -1) {
                    time += travel[last];
                }
                last = i - 1;
            }
        }
        return time;
    }

    public int MinTimeToCollectGarbage(List<string> garbage, List<int> travel) {
        return GetTime(garbage, travel, 'M') +
               GetTime(garbage, travel, 'P') +
               GetTime(garbage, travel, 'G');
    }

    public static void Main(string[] args) {
        var garbage = new List<string> { "MMM", "PGM", "GP" };
        var travel = new List<int> { 3, 10 };
        SolutionSep sol = new SolutionSep();
        Console.WriteLine(sol.MinTimeToCollectGarbage(garbage, travel)); // Output: 37
    }
}

For Python, we define a method get_time that extracts and counts each relevant garbage item across the list storing them, then sums the same. The straightforward in and count operations simplify this calculation, spread over different calls for separate types.

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.

TypeScript

function garbageCollection(garbage: string[], travel: number[]): number {
    const last: Map<string, number> = new Map();
    let ans = 0;
    for (let i = 0; i < garbage.length; ++i) {
        const s = garbage[i];
        ans += s.length;
        for (const c of s) {
            last.set(c, i);
        }
    }
    let ts = 0;
    for (let i = 1; i <= travel.length; ++i) {
        ts += travel[i - 1];
        for (const [_, j] of last) {
            if (i === j) {
                ans += ts;
            }
        }
    }
    return ans;
}

func garbageCollection(garbage []string, travel []int) (ans int) {
	last := map[byte]int{}
	for i, s := range garbage {
		ans += len(s)
		for j := range s {
			last[s[j]] = i
		}
	}
	ts := 0
	for i := 1; i <= len(travel); i++ {
		ts += travel[i-1]
		for _, j := range last {
			if i == j {
				ans += ts
			}
		}
	}
	return
}

Rust

use std::collections::HashMap;

impl Solution {
    pub fn garbage_collection(garbage: Vec<String>, travel: Vec<i32>) -> i32 {
        let mut last: HashMap<char, usize> = HashMap::new();
        let mut ans = 0;
        for (i, s) in garbage.iter().enumerate() {
            ans += s.len() as i32;
            for c in s.chars() {
                last.insert(c, i);
            }
        }
        let mut ts = 0;
        for (i, t) in travel.iter().enumerate() {
            ts += t;
            for &j in last.values() {
                if i + 1 == j {
                    ans += ts;
                }
            }
        }
        ans
    }
}

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 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	–

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

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

Minimum Amount of Time to Collect Garbage solution and explanation

The problem

Approach overview

Approach 1: Prefix Sum Method for Optimized Travel Calculation

Approach 2: Separate Calculation for Each Truck Type

Approach 3: Hash Table + Prefix Sum

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Amount of Time to Collect Garbage solution and explanation

The problem

Approach overview

Approach 1: Prefix Sum Method for Optimized Travel Calculation

Approach 2: Separate Calculation for Each Truck Type

Approach 3: Hash Table + Prefix Sum

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems