# 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& garbage, vector& travel) { vector 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& garbage, const vector& prefix, char c) { int characterCount = 0; int lastIndex = -1; for (int i = 0; i < garbage.size(); ++i) { const string& s = garbage[i]; if (any_of(s.begin(), s.end(), [c](const char g) { return g == c; })) lastIndex = i; characterCount += std::count(s.begin(), s.end(), 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')