Maximum Total Beauty of the Gardens - Solution & Explanation

Problem Overview: You are given an array where each value represents flowers already planted in a garden. You can add up to newFlowers flowers. A garden reaching target flowers becomes full and contributes full beauty. Incomplete gardens contribute partial beauty based on the minimum flower count among them. The goal is to distribute flowers to maximize total beauty.

Approach 1: Brute Force Distribution (Exponential / High Polynomial Time, O(n^2) or worse, O(1) space)

The naive idea is to try every possible distribution of newFlowers across gardens and compute the resulting beauty. For each configuration, count how many gardens reach target and compute the minimum value among the remaining gardens to determine the partial score. This approach requires exploring many allocation combinations and repeatedly recalculating minimum values. The search space grows extremely fast, making it infeasible for large inputs. It only helps reason about the scoring structure: some gardens should become fully complete while others should be balanced to maximize the minimum value.

Approach 2: Greedy Strategy with Sorting (O(n log n) time, O(n) space)

The optimal strategy separates gardens into two groups: those you fully complete and those you keep partial. Start by sorting the array so smaller gardens are handled first. For the partial group, the best move is to raise the smallest values as evenly as possible because the partial beauty depends on the minimum element. Using prefix sums over the sorted array allows you to compute how many flowers are required to raise the first k gardens to a specific level.

Next, iterate over how many gardens you convert to full. Each time you reserve flowers to reach target for the largest gardens. With the remaining flowers, maximize the minimum value among the remaining gardens. This step uses binary search to find the highest achievable minimum value that can be raised using prefix sums. The algorithm works because completing large gardens is often cheaper while raising smaller gardens improves the partial contribution.

This method combines greedy decisions, sorting to structure the search space, and prefix sums over the array to compute flower costs efficiently. By iterating possible counts of full gardens and optimizing the remainder, you evaluate all optimal beauty configurations without exploring every distribution.

Recommended for interviews: The greedy + sorting approach is the expected solution. Interviewers want to see that you recognize the split between full and partial gardens, then optimize the minimum partial value using prefix sums and binary search. Mentioning the brute force idea shows understanding of the scoring model, but implementing the greedy optimization demonstrates strong algorithmic reasoning.