Skip to content

2391. Minimum Amount of Time to Collect Garbage 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  int garbageCollection(vector<string>& garbage, vector<int>& travel) {
    vector<int> prefix(travel.size());
    partial_sum(travel.begin(), travel.end(), prefix.begin());
    const int timeM = getTime(garbage, prefix, 'M');
    const int timeP = getTime(garbage, prefix, 'P');
    const int timeG = getTime(garbage, prefix, 'G');
    return timeM + timeP + timeG;
  }

 private:
  int getTime(const vector<string>& garbage, const vector<int>& prefix,
              char c) {
    int characterCount = 0;
    int lastIndex = -1;
    for (int i = 0; i < garbage.size(); ++i) {
      const string& s = garbage[i];
      if (ranges::any_of(s, [c](const char g) { return g == c; }))
        lastIndex = i;
      characterCount += std::ranges::count(s, c);
    }
    return characterCount + (lastIndex <= 0 ? 0 : prefix[lastIndex - 1]);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public int garbageCollection(String[] garbage, int[] travel) {
    int[] prefix = new int[travel.length];
    prefix[0] = travel[0];
    for (int i = 1; i < prefix.length; ++i)
      prefix[i] += prefix[i - 1] + travel[i];
    final int timeM = getTime(garbage, prefix, 'M');
    final int timeP = getTime(garbage, prefix, 'P');
    final int timeG = getTime(garbage, prefix, 'G');
    return timeM + timeP + timeG;
  }

  private int getTime(String[] garbage, int[] prefix, char c) {
    int characterCount = 0;
    int lastIndex = -1;
    for (int i = 0; i < garbage.length; ++i) {
      final String s = garbage[i];
      if (s.chars().anyMatch(g -> g == c))
        lastIndex = i;
      characterCount += (int) s.chars().filter(g -> g == c).count();
    }
    return characterCount + (lastIndex <= 0 ? 0 : prefix[lastIndex - 1]);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def garbageCollection(self, garbage: list[str], travel: list[int]) -> int:
    prefix = list(itertools.accumulate(travel))

    def getTime(c: str) -> int:
      characterCount = 0
      lastIndex = -1
      for i, s in enumerate(garbage):
        if any(g == c for g in s):
          lastIndex = i
        characterCount += s.count(c)
      return characterCount + (0 if lastIndex <= 0 else prefix[lastIndex - 1])

    return getTime('M') + getTime('P') + getTime('G')