Minimum Number of Buckets Required to Collect Rainwater from Houses

Problem Description

Ah, the age-old dilemma of how to keep your houses dry while it rains! Imagine you’re living in a neighborhood where houses are lined up like ducks in a row, and you need to figure out how many buckets you need to place to collect rainwater. But wait! You can’t just throw buckets anywhere; they have to be strategically placed next to the houses. If you don’t, you might end up with a soggy mess that even the best of umbrellas can’t save you from.

In this problem, represented as a string, ‘H’ denotes a house, ‘B’ denotes a bucket, and ‘.’ denotes an empty space. Your mission, should you choose to accept it, is to determine the minimum number of buckets required to ensure that every house has a bucket next to it. If it’s impossible to do so, you’ll return -1.

Code Solution


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] == '.')
          street[i + 1] = 'B';
        else if (i > 0 && street[i - 1] == '.')
          street[i - 1] = 'B';
        else
          return -1;
      }
    return ranges::count(street, 'B');
  }
};

Approach Explanation

The approach here is as straightforward as a rainy day. The algorithm iterates through the string representing the street. For each house (‘H’), it checks if there’s already a bucket next to it. If not, it tries to place a bucket in the next available spot (preferably to the right). If that’s not possible, it checks to the left. If neither side is available, it returns -1, indicating that it’s impossible to place buckets for that house. Finally, it counts the total number of buckets placed.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the length of the street string. We traverse the string once.
Space Complexity	O(1), as we are using a constant amount of space for our operations.

Real-World Example

Picture this: You’re hosting a barbecue in your backyard, and the weather forecast says rain. You have a row of friends (houses) sitting on your patio, and you need to ensure they don’t get drenched. You can only place buckets (umbrellas) next to them. If you can’t find a spot for a bucket next to a friend, they might just leave your party early, and we can’t have that!