Minimum Amount of Time to Collect Garbage

Med

#2176Time: 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.

Patterns

Prefix Sum

Data structures

Array String

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

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

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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

1class Solution {2    public int garbageCollection(String[] garbage, int[] travel) {3        int n = garbage.length;4        long[] prefixTravel = new long[n];5        for (int i = 0; i < n - 1; i++) {6            prefixTravel[i + 1] = prefixTravel[i] + travel[i];7        }8 9        int pickingTime = 0;10        int lastM = 0;11        int lastP = 0;12        int lastG = 0;13 14        for (int i = 0; i < n; i++) {15            String s = garbage[i];16            pickingTime += s.length();17            for (char c : s.toCharArray()) {18                if (c == 'M') lastM = i;19                else if (c == 'P') lastP = i;20                else if (c == 'G') lastG = i;21            }22        }23 24        long travelTime = prefixTravel[lastM] + prefixTravel[lastP] + prefixTravel[lastG];25        return (int) (pickingTime + travelTime);26    }27}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.
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.
Final Result: The minimum time is the sum of the total picking time and the total travel time.

1class Solution {2    public int garbageCollection(String[] garbage, int[] travel) {3        int n = garbage.length;4        int pickingTime = 0;5        int lastM = 0, lastP = 0, lastG = 0;6 7        // First pass: find last indices and total picking time8        for (int i = 0; i < n; i++) {9            String s = garbage[i];10            pickingTime += s.length();11            for (char c : s.toCharArray()) {12                if (c == 'M') lastM = i;13                else if (c == 'P') lastP = i;14                else if (c == 'G') lastG = i;15            }16        }17 18        int travelTime = 0;19        // Second part: calculate travel time20        for (int i = 0; i < lastM; i++) {21            travelTime += travel[i];22        }23        for (int i = 0; i < lastP; i++) {24            travelTime += travel[i];25        }26        for (int i = 0; i < lastG; i++) {27            travelTime += travel[i];28        }29 30        return pickingTime + travelTime;31    }32}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1public class Solution {2    public int GarbageCollection(string[] garbage, int[] travel) {3        int len = garbage.Length;4        int res = 0;5        HashSet < char > s = new HashSet < char > ();6        for (int i = len - 1; i >= 0; i--) {7            foreach(char ch in garbage[i].ToCharArray()) {8                if (!s.Contains(ch)) s.Add(ch);9            }10            res += garbage[i].Length;11            res += i > 0 ? s.Count * travel[i - 1] : 0;12        }13        return res;14    }15}

1class Solution {2public3  int garbageCollection(String[] garbage, int[] travel) {4    int[] last = new int[26];5    int n = garbage.length;6    int ans = 0;7    for (int i = 0; i < n; ++i) {8      int k = garbage[i].length();9      ans += k;10      for (int j = 0; j < k; ++j) {11        last[garbage[i].charAt(j) - 'A'] = i;12      }13    }14    int m = travel.length;15    int[] s = new int[m + 1];16    for (int i = 0; i < m; ++i) {17      s[i + 1] = s[i] + travel[i];18    }19    for (int i : last) {20      ans += s[i];21    }22    return ans;23  }24}

1class Solution {2public:3  int garbageCollection(vector<string> &garbage, vector<int> &travel) {4    int n = garbage.size(), m = travel.size();5    int last[26]{};6    int ans = 0;7    for (int i = 0; i < n; ++i) {8      ans += garbage[i].size();9      for (char &c : garbage[i]) {10        last[c - 'A'] = i;11      }12    }13    int s[m + 1];14    s[0] = 0;15    for (int i = 1; i <= m; ++i) {16      s[i] = s[i - 1] + travel[i - 1];17    }18    for (int i : last) {19      ans += s[i];20    }21    return ans;22  }23};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1public class Solution {2    public int GarbageCollection(string[] garbage, int[] travel) {3        int len = garbage.Length;4        int res = 0;5        HashSet < char > s = new HashSet < char > ();6        for (int i = len - 1; i >= 0; i--) {7            foreach(char ch in garbage[i].ToCharArray()) {8                if (!s.Contains(ch)) s.Add(ch);9            }10            res += garbage[i].Length;11            res += i > 0 ? s.Count * travel[i - 1] : 0;12        }13        return res;14    }15}

1class Solution {2public3  int garbageCollection(String[] garbage, int[] travel) {4    int[] last = new int[26];5    int n = garbage.length;6    int ans = 0;7    for (int i = 0; i < n; ++i) {8      int k = garbage[i].length();9      ans += k;10      for (int j = 0; j < k; ++j) {11        last[garbage[i].charAt(j) - 'A'] = i;12      }13    }14    int m = travel.length;15    int[] s = new int[m + 1];16    for (int i = 0; i < m; ++i) {17      s[i + 1] = s[i] + travel[i];18    }19    for (int i : last) {20      ans += s[i];21    }22    return ans;23  }24}

1class Solution {2public:3  int garbageCollection(vector<string> &garbage, vector<int> &travel) {4    int n = garbage.size(), m = travel.size();5    int last[26]{};6    int ans = 0;7    for (int i = 0; i < n; ++i) {8      ans += garbage[i].size();9      for (char &c : garbage[i]) {10        last[c - 'A'] = i;11      }12    }13    int s[m + 1];14    s[0] = 0;15    for (int i = 1; i <= m; ++i) {16      s[i] = s[i - 1] + travel[i - 1];17    }18    for (int i : last) {19      ans += s[i];20    }21    return ans;22  }23};

1class Solution:2    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

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.