2391. Minimum Amount of Time to Collect Garbage

Problem Description

In this problem, we are managing waste collection for a city with a uniquely efficient garbage collection system. There is a row of houses numbered from 0, and at each house, there's a certain amount of metal (M), paper (P), and glass (G) waste. The waste at each house is provided to us in an array garbage where each string consists of letters 'M', 'P', and 'G', representing the types of garbage at that house.

We also have information on travel times between houses, given by the travel array. travel[i] tells us the time it takes to travel from house i to house i+1.

The city has three garbage trucks, each designated to collect one type of garbage. All trucks start collecting from house 0, but not every truck has to visit every house. The trucks move in order of the house numbers, but a truck only needs to visit a house if there is garbage for it to collect there. At any point in time, only one truck can be active, meaning the other two can't collect or move while one is in operation.

The goal is to determine the minimum total time required to collect all the garbage from all the houses.

Intuition

To solve this problem, an efficient approach involves considering two key components. Firstly, we need to calculate the total time spent collecting garbage, which is the sum of garbage units since each unit takes one minute to be collected. Secondly, we must track the furthest each truck travels since the trucks only need to travel as far as the last house that has garbage for them.

The solution is implemented in the following steps:

We start by initializing a variable ans to zero, which will accumulate the total time.
We create a dictionary last to record the index of the last house that contains each type of garbage.
We iterate over the garbage array, adding the length of each string to ans, which corresponds to the collection time at that house. During this iteration, we also update the last dictionary for each type of garbage encountered.
The travel time for each truck will only need to include the distance to the furthest house for its type of garbage. To simplify the calculation, we create a cumulative sum array s of the travel array times.
We add to ans the cumulative travel times of the furthest house for each garbage type by summing the corresponding travel times from the s array.
Finally, we return the resulting ans, which now represents the minimum number of minutes needed to collect all the garbage.

Learn more about Prefix Sum patterns.

Solution Approach

The implementation of the solution can be broken down into multiple parts, aligning with the intuition detailed above. Here's a step-by-step approach to how the solution works:

Initialization of variables:
- We initialize an answer variable ans to 0. This will accumulate the total time spent collecting garbage and traveling.
- A dictionary last is created to keep track of the last occurrence of each garbage type. The keys will be 'M', 'P', and 'G', and the values will be the indices of the last house that contains the corresponding type of garbage.
Iterating through garbage array:
- We iterate over the garbage array with enumerate() to have both the index i and the garbage string s.
- We add the length of s to ans, since each garbage unit takes one minute to collect.
- Within the same loop, we iterate through each character c in the string s. For each character, we update the last dictionary: last[c] = i. This means for each type of garbage, we're keeping the index of the last house where it has to be collected.
Calculating travel time:
- We use Python's accumulate function from the itertools module with an initial parameter set to 0, to create a cumulative sum array s from the travel array. This accumulation includes the time it takes to travel from house 0 to every other house.
- We then add the total travel time for each garbage truck by summing the travel time (from the array s) up to the last house that requires its service: sum(s[i] for i in last.values()). This is added to the ans.
Return the total time:
- Finally, we return the accumulated answer ans, which now contains the total number of minutes spent collecting all the garbage and the travel time for each truck to reach the last house where its service is needed.

This solution takes advantage of simple iterations through the garbage array to determine the total collection time, and the use of a cumulative sum array to efficiently calculate the travel times required for each type of garbage truck. This approach ensures that all garbage is collected in the minimum amount of time possible by optimizing travel for each garbage truck.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution with a small example:

Suppose we have a row of four houses numbered from 0 to 3, and the contents of their garbage bins are as follows:

House 0 has "MPG" (Metal, Paper, Glass)
House 1 has "PP" (Paper)
House 2 has "GP" (Glass, Paper)
House 3 has "M" (Metal)

The garbage array for these houses would be: ["MPG", "PP", "GP", "M"].

The travel time between the houses is given by the travel array: [2, 4, 3] which indicates it takes 2 minutes to travel from House 0 to House 1, 4 minutes from House 1 to House 2, and 3 minutes from House 2 to House 3.

Following the solution approach:

Initialization of variables:
- ans is initialized to 0.
- last is initialized to {}, which will be used to store the last occurrences of 'M', 'P', and 'G'.
Iterating through garbage array:
- At House 0, "MPG" adds 3 minutes to ans, and last is updated to {'M': 0, 'P': 0, 'G': 0}.
- At House 1, "PP" adds 2 minutes to ans, and last is updated to {'M': 0, 'P': 1, 'G': 0}.
- At House 2, "GP" adds 2 minutes to ans, and last is updated to {'M': 0, 'P': 2, 'G': 2}.
- At House 3, "M" adds 1 minute to ans, and last is updated to {'M': 3, 'P': 2, 'G': 2}.
Calculating travel time:
- The cumulative sum array s from travel plus an initial 0 is calculated: [0, 2, 6, 9] (using the itertools.accumulate function).
- We add the travel times for each truck to ans. For 'M', we add s[3] (3 minutes). For 'P', we add s[2] (6 minutes). For 'G', we add s[2] (6 minutes).
Return the total time:
- The ans after adding travel times is ans += 3 + 6 + 6.
- ans is initially 8, and after adding travel times, it becomes 23.

Hence, the minimum total time required to collect all the garbage from all the houses is 23 minutes.

Solution Implementation

1class Solution:
2    def garbageCollection(self, garbage: List[str], travel: List[int]) -> int:
3        """
4        Calculate the minimum amount of time to collect garbage.
5
6        Args:
7        garbage: A list of strings representing the content of garbage collected on each day.
8        travel: A list of integers representing the amount of time needed to travel between adjacent houses.
9
10        Returns:
11        The minimum amount of time needed to collect all the garbage.
12        """
13      
14        # Initialize the total collection time
15        total_time = 0
16
17        # Dictionary to store the last index where 'G', 'P', or 'M' appears
18        last_index = {}
19
20        # Calculate the total time to pick up all the garbage
21        # and track the last occurrence of each type of garbage
22        for i, bags in enumerate(garbage):
23            # Add the time to collect garbage at this index
24            total_time += len(bags)
25
26            # Update the last seen index for each garbage type in the bags
27            for type_garbage in bags:
28                last_index[type_garbage] = i
29
30        # Calculate the prefix sum of travel time for quick lookup
31        prefix_sum_travel = list(accumulate(travel, initial=0))
32
33        # Add the travel time to the last occurrence of each garbage type
34        total_time += sum(prefix_sum_travel[i] for i in last_index.values())
35
36        return total_time
37

1class Solution {
2    public int garbageCollection(String[] garbage, int[] travel) {
3        // lastPositionOf holds the last position where each type of garbage appears
4        int[] lastPositionOf = new int[26];
5        int numberOfHouses = garbage.length;
6        int totalTime = 0;
7
8        // Calculate the total amount of garbage and update the last position for each garbage type
9        for (int i = 0; i < numberOfHouses; ++i) {
10            int garbageAtHouse = garbage[i].length();
11            totalTime += garbageAtHouse; // Collect garbage at current house
12            // Update the last position for each type of garbage in current house
13            for (int j = 0; j < garbageAtHouse; ++j) {
14                lastPositionOf[garbage[i].charAt(j) - 'A'] = i;
15            }
16        }
17
18        // Calculate the prefix sum of travel time between the houses
19        int[] prefixSumOfTravel = new int[travel.length + 1];
20        for (int i = 0; i < travel.length; ++i) {
21            prefixSumOfTravel[i + 1] = prefixSumOfTravel[i] + travel[i];
22        }
23
24        // Add the travel time for each garbage truck to reach the last house of its type
25        for (int lastPosition : lastPositionOf) {
26            if(lastPosition != 0) { // Only add travel time if the garbage type was present
27                totalTime += prefixSumOfTravel[lastPosition];
28            }
29        }
30
31        // Return the total time to collect all garbage and return
32        return totalTime;
33    }
34}
35

1class Solution {
2public:
3    int garbageCollection(vector<string>& garbage, vector<int>& travel) {
4        // Get the number of garbage bags and the number of travel times.
5        int garbageCount = garbage.size();
6        int travelCount = travel.size();
7      
8        // Initialize an array to keep track of the last occurrence position of each type of garbage ('A' to 'Z').
9        int lastPosition[26] = {};
10      
11        // Initialize total time taken to collect garbage to 0.
12        int totalTime = 0;
13      
14        // Iterate through all the piles of garbage to perform initial collection and record the last occurrence.
15        for (int i = 0; i < garbageCount; ++i) {
16            // Add the size of the current pile to the total time (as it represents direct collection time).
17            totalTime += garbage[i].size();
18            // Update the last occurrence position for each type of garbage found in the current pile.
19            for (char& c : garbage[i]) {
20                lastPosition[c - 'A'] = i;
21            }
22        }
23      
24        // Initialize a prefix sum array to store the cumulative travel time to reach each house.
25        int cumulativeTravel[travelCount + 1];
26        cumulativeTravel[0] = 0;
27      
28        for (int i = 1; i <= travelCount; ++i) {
29            cumulativeTravel[i] = cumulativeTravel[i - 1] + travel[i - 1];
30        }
31      
32        // Add the necessary travel time for each type of garbage to the total time.
33        for (int i : lastPosition) {
34            if (i != 0) { // Non-zero position means the garbage type was present and needs to be collected.
35                totalTime += cumulativeTravel[i];
36            }
37        }
38      
39        // Return the total time taken for garbage collection.
40        return totalTime;
41    }
42};
43

1function garbageCollection(garbage: string[], travel: number[]): number {
2    // The number of houses
3    const numHouses = garbage.length;
4    // The number of travel segments
5    const numTravelSegments = travel.length;
6    // Initialize the total time to 0
7    let totalTime = 0;
8    // Array to store the last house visited for each kind of garbage (26 represents 26 letters)
9    const lastVisited = new Array(26).fill(0);
10  
11    // Traverse through garbage bins of each house
12    for (let i = 0; i < numHouses; ++i) {
13        // Add the garbage collection time which is equal to the garbage amount
14        totalTime += garbage[i].length;
15        // Record the last house visited for each kind of garbage
16        for (const character of garbage[i]) {
17            lastVisited[character.charCodeAt(0) - 'A'.charCodeAt(0)] = i;
18        }
19    }
20  
21    // Prefix sum array to store cumulative travel time between houses
22    const cumulativeTravelTime = new Array(numTravelSegments + 1).fill(0);
23    for (let i = 1; i <= numTravelSegments; ++i) {
24        cumulativeTravelTime[i] = cumulativeTravelTime[i - 1] + travel[i - 1];
25    }
26  
27    // Calculate the extra travel time for each kind of garbage based on the last visited house
28    for (const houseIndex of lastVisited) {
29        totalTime += cumulativeTravelTime[houseIndex];
30    }
31  
32    // Return the total time spent
33    return totalTime;
34}
35

Time and Space Complexity

Time Complexity

The time complexity of the given code can be analyzed based on its two main operations.

The first loop iterates over the list garbage once, making its time complexity O(N) where N is the number of elements in garbage. Within this loop, there is another loop that iterates over each character in strings of garbage. In the worst case, the length of all garbage strings combined is M (assuming M to be the sum of lengths of all strings in garbage), so this part runs in O(M) time.
The second part of the code uses the built-in function accumulate() to create list s from travel, which runs in O(T) time where T is the number of elements in travel.
The summing up of s[i] for i in last.values() has a worst case of O(K) where K is the number of unique characters (i.e., 'G', 'M', 'P' in the garbage collection problem). However, since K is small and constant (at most 3 in this specific scenario), this can be considered O(1).

Overall, the time complexity of the function is O(N + M + T + K) which simplifies to O(N + M + T) since K is small and constant.

Space Complexity

As for space complexity:

The last dictionary potentially holds last indices for each type of garbage. Since the input problem is limited to three types of garbage at most, this dictionary's size is O(K), which is considered O(1) because K is small and constant.
The list s is created using the accumulate() function on the travel list, so its space is O(T) where T is the number of elements in travel.

Therefore, the space complexity of the code is O(T) because the constant space for last is negligible.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know