# Minimum Amount of Time to Collect Garbage
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-amount-of-time-to-collect-garbage)
Canonical: https://scaleengineer.com/dsa/problems/minimum-amount-of-time-to-collect-garbage
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, String
---
## Problem
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 <= 105`
* `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`

# Approaches
## Naive Simulation per Truck
This approach directly simulates the process for each of the three garbage trucks independently and then sums up their individual times. For each type of garbage (Metal, Paper, and Glass), we calculate the total time it would take for its corresponding truck.
**Time:** O(N * M), where N is the number of houses and M is the maximum length of a garbage string. For each of the 3 garbage types, we might scan the entire `garbage` array to find the last house (O(N*M)) and then scan again to calculate picking and travel time (O(N*M)). This leads to an overall complexity dominated by these repeated, nested operations. · **Space:** O(1) extra space, as we only use a few variables to store intermediate results.
**Pros:** Conceptually simple and directly follows the problem statement's breakdown.; Uses constant extra space.
**Cons:** Highly inefficient due to multiple full or partial traversals of the input arrays for each garbage type.; Redundant calculations: travel path sums are recalculated, and picking time is calculated by iterating through all garbage strings three times instead of once.
### Explanation
The total time is the sum of the time taken by the Metal, Paper, and Glass trucks. To calculate the time for a single truck, say the Metal one, we perform the following steps:
1.  First, we determine the last house the truck must visit. This is done by searching from the last house backwards to find one with Metal garbage.
2.  Then, we calculate the time spent picking up garbage. This involves iterating from house 0 up to this last house and counting all units of Metal garbage.
3.  Finally, we calculate the travel time by summing the `travel` array values up to the last house.
This entire process is repeated for the Paper and Glass trucks. The main drawback is the redundant work, as we iterate over the `garbage` and `travel` arrays multiple times.
### Algorithm
- Initialize `totalMinutes = 0`.
- Define an array of garbage types: `{'M', 'P', 'G'}`.
- Loop through each garbage `type`:
  - Find the index of the `lastHouse` that contains the current `type` of garbage by iterating through the `garbage` array backwards. If no such house is found, skip to the next type.
  - If a `lastHouse` is found, initialize `pickingTimeForType = 0` and `travelTimeForType = 0`.
  - Iterate from house `i = 0` up to `lastHouse`:
    - Count the number of characters equal to `type` in `garbage[i]` and add it to `pickingTimeForType`.
    - The total travel time to reach house `i` is the sum of `travel[0]` to `travel[i-1]`. We can calculate this cumulatively.
  - The total time for this truck is the sum of its picking time and its total travel time to its last house. Add this to `totalMinutes`.
- After iterating through all types, return `totalMinutes`.

## Prefix Sum Optimization
This approach improves upon the naive method by pre-calculating the travel times. The total time is the sum of the total picking time and the travel times for each of the three trucks. The travel time for a truck to reach a specific house can be found efficiently using a prefix sum array.
**Time:** O(N + L), where N is the number of houses and L is the total number of garbage items (total characters). O(N) is for building the prefix sum array, and O(L) is for iterating through all garbage items to find picking time and last indices. This is linear in the size of the input. · **Space:** O(N) for the prefix sum array, where N is the number of houses.
**Pros:** Efficient time complexity as it processes the garbage and travel information in separate, non-nested loops.; Travel time lookups become O(1) operations after the initial setup.
**Cons:** Requires extra space proportional to the number of houses, which can be large.
### Explanation
1.  First, we create a prefix sum array for the `travel` times. `prefixTravel[i]` will store the total time to travel from house 0 to house `i`. This allows us to find the travel time to any house in O(1) time.
2.  Next, we iterate through the `garbage` array once to find two things:
    a. The total picking time, which is the sum of the lengths of all strings in `garbage`.
    b. The index of the last house that contains each type of garbage ('M', 'P', 'G'). We maintain three variables, `lastM`, `lastP`, and `lastG`, and update them as we iterate.
3.  Finally, we calculate the total time. It's the sum of the total picking time and the travel times for each truck. The travel time for the metal truck is `prefixTravel[lastM]`, for the paper truck is `prefixTravel[lastP]`, and for the glass truck is `prefixTravel[lastG]`.
```java
class Solution {
    public int garbageCollection(String[] garbage, int[] travel) {
        int n = garbage.length;
        long[] prefixTravel = new long[n];
        for (int i = 0; i < n - 1; i++) {
            prefixTravel[i + 1] = prefixTravel[i] + travel[i];
        }

        int pickingTime = 0;
        int lastM = 0;
        int lastP = 0;
        int lastG = 0;

        for (int i = 0; i < n; i++) {
            String s = garbage[i];
            pickingTime += s.length();
            for (char c : s.toCharArray()) {
                if (c == 'M') lastM = i;
                else if (c == 'P') lastP = i;
                else if (c == 'G') lastG = i;
            }
        }

        long travelTime = prefixTravel[lastM] + prefixTravel[lastP] + prefixTravel[lastG];
        return (int) (pickingTime + travelTime);
    }
}
```
### Algorithm
- Create a prefix sum array, `prefixTravel`, of size `N` (number of houses).
- Initialize `prefixTravel[0] = 0`. Then, for `i` from 0 to `N-2`, calculate `prefixTravel[i+1] = prefixTravel[i] + travel[i]`. This stores the time to travel from house 0 to any house `i+1`.
- Initialize `totalPickingTime = 0` and `lastM`, `lastP`, `lastG` to 0.
- Iterate through the `garbage` array from `i = 0` to `N-1`:
  - Add the length of `garbage[i]` to `totalPickingTime`.
  - Check for 'M', 'P', 'G' in `garbage[i]`. If a type is found, update its corresponding last index variable (`lastM`, `lastP`, or `lastG`) to `i`.
- Calculate the total travel time by summing the pre-calculated travel times for each truck: `travelTime = prefixTravel[lastM] + prefixTravel[lastP] + prefixTravel[lastG]`.
- The final result is `totalPickingTime + travelTime`.

## Two Passes with Constant Space
This is the most optimal approach in terms of both time and space. It separates the calculation into two main parts: one pass to gather information about garbage distribution and a second part to calculate travel times. This avoids the O(N) space complexity of the prefix sum approach while maintaining a similar time efficiency.
**Time:** O(N + L), where N is the number of houses and L is the total number of garbage items. The first pass takes O(L) time. The second part takes at most O(3*N) time. The overall complexity is linear. · **Space:** O(1) extra space, as it only requires a few variables to store the last indices and running totals.
**Pros:** Optimal time complexity, linear in the input size.; Optimal space complexity, using only a constant amount of extra space.
**Cons:** Requires two passes over the data, which might be slightly less cache-friendly than a true single-pass solution, though the performance difference is often negligible.
### Explanation
1.  **First Pass (Garbage Information):** We iterate through the `garbage` array from house 0 to `N-1`. In this pass, we do two things simultaneously: calculate the total picking time by summing up the number of garbage items at each house (`garbage[i].length`), and find the index of the last house for each garbage type by keeping track of the latest index `i` where 'M', 'P', or 'G' garbage is found.
2.  **Second Pass (Travel Time Calculation):** After the first pass, we have the total picking time and the final destinations for each truck. We then calculate the total travel time. Instead of using a prefix sum array, we simply sum the `travel` costs for each truck individually. For the metal truck, we sum `travel[j]` from `j=0` to `lastM - 1`, and do similarly for paper and glass trucks. Summing these three gives the total travel time.
3.  **Final Result:** The minimum time is the sum of the total picking time and the total travel time.
```java
class Solution {
    public int garbageCollection(String[] garbage, int[] travel) {
        int n = garbage.length;
        int pickingTime = 0;
        int lastM = 0, lastP = 0, lastG = 0;

        // First pass: find last indices and total picking time
        for (int i = 0; i < n; i++) {
            String s = garbage[i];
            pickingTime += s.length();
            for (char c : s.toCharArray()) {
                if (c == 'M') lastM = i;
                else if (c == 'P') lastP = i;
                else if (c == 'G') lastG = i;
            }
        }

        int travelTime = 0;
        // Second part: calculate travel time
        for (int i = 0; i < lastM; i++) {
            travelTime += travel[i];
        }
        for (int i = 0; i < lastP; i++) {
            travelTime += travel[i];
        }
        for (int i = 0; i < lastG; i++) {
            travelTime += travel[i];
        }

        return pickingTime + travelTime;
    }
}
```
### Algorithm
- **Pass 1: Garbage Analysis**
  - Initialize `totalPickingTime = 0` and `lastM`, `lastP`, `lastG` to 0.
  - Iterate through the `garbage` array from house `i = 0` to `N-1`:
    - Add the length of `garbage[i]` to `totalPickingTime`.
    - Iterate through the characters of `garbage[i]`. If 'M' is found, update `lastM = i`. Do the same for 'P' and 'G'.
- **Pass 2: Travel Time Calculation**
  - Initialize `totalTravelTime = 0`.
  - Sum the travel costs for each truck up to its last required stop:
    - Add `travel[i]` for `i` from 0 to `lastM - 1` to `totalTravelTime`.
    - Add `travel[i]` for `i` from 0 to `lastP - 1` to `totalTravelTime`.
    - Add `travel[i]` for `i` from 0 to `lastG - 1` to `totalTravelTime`.
- **Result**
  - Return `totalPickingTime + totalTravelTime`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int GarbageCollection(string[] garbage, int[] travel) {
        int len = garbage.Length;
        int res = 0;
        HashSet < char > s = new HashSet < char > ();
        for (int i = len - 1; i >= 0; i--) {
            foreach(char ch in garbage[i].ToCharArray()) {
                if (!s.Contains(ch)) s.Add(ch);
            }
            res += garbage[i].Length;
            res += i > 0 ? s.Count * travel[i - 1] : 0;
        }
        return res;
    }
}
```

### Java

```java
class Solution {
public
  int garbageCollection(String[] garbage, int[] travel) {
    int[] last = new int[26];
    int n = garbage.length;
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      int k = garbage[i].length();
      ans += k;
      for (int j = 0; j < k; ++j) {
        last[garbage[i].charAt(j) - 'A'] = i;
      }
    }
    int m = travel.length;
    int[] s = new int[m + 1];
    for (int i = 0; i < m; ++i) {
      s[i + 1] = s[i] + travel[i];
    }
    for (int i : last) {
      ans += s[i];
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int garbageCollection(vector<string> &garbage, vector<int> &travel) {
    int n = garbage.size(), m = travel.size();
    int last[26]{};
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      ans += garbage[i].size();
      for (char &c : garbage[i]) {
        last[c - 'A'] = i;
      }
    }
    int s[m + 1];
    s[0] = 0;
    for (int i = 1; i <= m; ++i) {
      s[i] = s[i - 1] + travel[i - 1];
    }
    for (int i : last) {
      ans += s[i];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int: ans = 0 last = {} for i, s in enumerate(garbage): ans += len(s) for c in s: last[c] = i s = list(accumulate(travel, initial=0)) ans += sum(s[i] for i in last . values()) return ans

```