2391. Minimum Amount of Time to Collect Garbage

MediumArrayStringPrefix Sum
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which type of traversal does breadth first search do?

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:

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

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

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

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

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

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

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:

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

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

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

  4. 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
Not Sure What to Study? Take the 2-min Quiz：

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

Time and Space Complexity

Time Complexity

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

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

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

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

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

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

Fast Track Your Learning with Our Quick Skills Quiz:

How many times is a tree node visited in a depth first search?

Recommended Readings

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫