Skip to content

2086. Minimum Number of Buckets Required to Collect Rainwater from Houses 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  int minimumBuckets(string street) {
    for (int i = 0; i < street.length(); ++i)
      if (street[i] == 'H') {
        if (i > 0 && street[i - 1] == 'B')
          continue;
        if (i + 1 < street.length() && street[i + 1] == '.')
          // always prefer place a bucket in (i + 1) because it enhance the
          // possibility to collect the upcoming house
          street[i + 1] = 'B';
        else if (i > 0 && street[i - 1] == '.')
          street[i - 1] = 'B';
        else
          return -1;
      }

    return count(begin(street), end(street), 'B');
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public int minimumBuckets(String street) {
    final char[] A = street.toCharArray();

    for (int i = 0; i < A.length; ++i)
      if (A[i] == 'H') {
        if (i > 0 && A[i - 1] == 'B')
          continue;
        if (i + 1 < A.length && A[i + 1] == '.')
          // always prefer place a bucket in (i + 1) because it enhance the
          // possibility to collect the upcoming house
          A[i + 1] = 'B';
        else if (i > 0 && A[i - 1] == '.')
          A[i - 1] = 'B';
        else
          return -1;
      }

    return (int) new String(A).chars().filter(a -> a == 'B').count();
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def minimumBuckets(self, street: str) -> int:
    A = list(street)

    for i, c in enumerate(A):
      if c == 'H':
        if i > 0 and A[i - 1] == 'B':
          continue
        if i + 1 < len(A) and A[i + 1] == '.':
          # always prefer place a bucket in (i + 1) because it enhance the
          # possibility to collect the upcoming house
          A[i + 1] = 'B'
        elif i > 0 and A[i - 1] == '.':
          A[i - 1] = 'B'
        else:
          return -1

    return A.count('B')