Problem Description

Alice manages n gardens and wants to maximize their total beauty by planting additional flowers.

You're given:

• An array flowers where flowers[i] represents the number of flowers already planted in garden i (these cannot be removed)
• newFlowers: the maximum number of additional flowers Alice can plant
• target: the minimum number of flowers needed for a garden to be considered "complete"
• full: the beauty value contributed by each complete garden
• partial: the beauty value multiplier for the minimum flower count among incomplete gardens

A garden is complete if it has at least target flowers. The total beauty is calculated as:

• Number of complete gardens × full
• Plus: Minimum flower count among all incomplete gardens × partial (or 0 if all gardens are complete)

The goal is to distribute up to newFlowers additional flowers among the gardens to maximize the total beauty.

For example, if you have 3 gardens with [1, 2, 4] flowers, target = 4, full = 5, partial = 2, and newFlowers = 3:

• Garden 2 already has 4 flowers (complete)
• You could add 2 flowers to garden 1 to make it complete (having 4 flowers)
• This would give: 2 complete gardens × 5 + minimum of remaining incomplete gardens (2) × 2 = 10 + 4 = 14 total beauty
• Alternatively, you could distribute flowers to increase the minimum among incomplete gardens for a different beauty value

The challenge is finding the optimal balance between creating more complete gardens versus increasing the minimum flower count in incomplete gardens to maximize the total beauty score.

Intuition

The key insight is recognizing that we face a trade-off: we can either use our additional flowers to create more complete gardens (earning full points each) or increase the minimum flower count among incomplete gardens (earning partial points per flower in the minimum garden).

First, we should sort the gardens by their current flower count. This helps us identify which gardens are easiest to complete (those closest to target) and which incomplete gardens we can efficiently boost together.

Why enumerate the number of complete gardens? Since we want to maximize beauty, we need to try different configurations. If we decide to have x complete gardens, we should complete the x gardens that already have the most flowers - this minimizes the cost and leaves more flowers for boosting incomplete gardens.

For each configuration with x complete gardens:

1. We complete the rightmost x gardens in our sorted array (they need the fewest additional flowers)
2. With the remaining flowers, we want to maximize the minimum among the incomplete gardens

The second part is clever: to maximize the minimum efficiently, we should bring all gardens up to the same level together. If we have gardens with [1, 2, 3] flowers and want to increase the minimum, we should first bring them all to 3, then all to 4, and so on. This is why we use binary search - to find the highest level we can afford to bring a group of gardens to.

The binary search finds the largest prefix of incomplete gardens we can afford to level up to the same height. The cost to bring gardens 0 to mid up to height flowers[mid] is flowers[mid] * (mid + 1) - sum(flowers[0:mid+1]). If we have extra flowers after this leveling, we can increase all these gardens further by dividing the remaining flowers equally among them.

By trying all possible values of x (number of complete gardens) and finding the optimal minimum for incomplete gardens in each case, we guarantee finding the maximum total beauty.

Learn more about Greedy, Two Pointers, Binary Search, Prefix Sum and Sorting patterns.

Solution Approach

First, we sort the flowers array to group gardens by their current flower counts. We also create a prefix sum array s to efficiently calculate range sums later.

flowers.sort()
n = len(flowers)
s = list(accumulate(flowers, initial=0))

We find the initial number of complete gardens using binary search:

i = n - bisect_left(flowers, target)

This tells us how many gardens already have at least target flowers.

Now we enumerate the number of complete gardens from i to n:

For each choice of x complete gardens:

1. Calculate cost to complete gardens: The garden at position n-x needs max(target - flowers[n-x], 0) additional flowers. We subtract this from newFlowers.

2. If we run out of flowers, we break since we can't achieve more complete gardens.

3. Binary search for optimal incomplete garden configuration: Among the remaining n-x incomplete gardens, we find the maximum index l where we can afford to bring all gardens [0...l] to the same level as flowers[l].

   The binary search checks: can we afford to bring gardens [0...mid] to level flowers[mid]?

   • Cost = flowers[mid] * (mid + 1) - s[mid + 1]
   • This represents: (target level × number of gardens) - (current total flowers in those gardens)

4. Calculate the minimum flower count y:

   • If l = -1, all incomplete gardens would need more flowers than available, so y = 0
   • Otherwise, after leveling gardens [0...l] to flowers[l], we have newFlowers - cost flowers left
   • We can increase all l+1 gardens by (newFlowers - cost) // (l + 1) flowers each
   • The final minimum is min(flowers[l] + increase, target - 1) (capped at target-1 to keep them incomplete)

5. Calculate beauty: x * full + y * partial

The algorithm returns the maximum beauty found across all configurations.

The time complexity is O(n² log n) where the outer loop runs O(n) times and each iteration performs a binary search O(log n) with O(n) validation in the worst case. The space complexity is O(n) for the prefix sum array.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Input:

• flowers = [2, 4, 5, 3]
• newFlowers = 10
• target = 6
• full = 20
• partial = 5

Step 1: Sort and Setup After sorting: flowers = [2, 3, 4, 5] Prefix sum array: s = [0, 2, 5, 9, 14]

Step 2: Find Initial Complete Gardens Using binary search, we find that garden at index 3 (with 5 flowers) is the only one close to being complete. So initially, i = 1 (we can try having 1 to 4 complete gardens).

Step 3: Enumerate Complete Garden Configurations

Configuration 1: x = 1 complete garden (completing the rightmost garden)

• Garden at index 3 needs 6 - 5 = 1 flower to complete
• Remaining flowers: 10 - 1 = 9
• Incomplete gardens: [2, 3, 4] at indices 0, 1, 2
• Binary search to maximize minimum:
  • Can we bring all 3 gardens to level 4? Cost = 4 × 3 - (2+3+4) = 12 - 9 = 3 ✓
  • After bringing all to level 4, we have 9 - 3 = 6 flowers left
  • We can add 6 // 3 = 2 flowers to each, making them all have 6 flowers
  • But wait! 6 would make them complete, so cap at target - 1 = 5
• Minimum among incomplete: 5
• Beauty: 1 × 20 + 5 × 5 = 45

Configuration 2: x = 2 complete gardens

• Gardens at indices 2 and 3 need (6-4) + (6-5) = 3 flowers total
• Remaining flowers: 10 - 3 = 7
• Incomplete gardens: [2, 3] at indices 0, 1
• Binary search to maximize minimum:
  • Can we bring both to level 3? Cost = 3 × 2 - (2+3) = 6 - 5 = 1 ✓
  • After bringing both to level 3, we have 7 - 1 = 6 flowers left
  • We can add 6 // 2 = 3 flowers to each, making them both have 6 flowers
  • Cap at target - 1 = 5
• Minimum among incomplete: 5
• Beauty: 2 × 20 + 5 × 5 = 65

Configuration 3: x = 3 complete gardens

• Gardens at indices 1, 2, 3 need (6-3) + (6-4) + (6-5) = 6 flowers total
• Remaining flowers: 10 - 6 = 4
• Incomplete gardens: [2] at index 0
• We can add all 4 flowers to this garden: 2 + 4 = 6
• But 6 would make it complete, so cap at 5
• Minimum among incomplete: 5
• Beauty: 3 × 20 + 5 × 5 = 85

Configuration 4: x = 4 complete gardens

• All gardens need to be complete
• Cost: (6-2) + (6-3) + (6-4) + (6-5) = 4 + 3 + 2 + 1 = 10 flowers
• Remaining flowers: 10 - 10 = 0 ✓
• No incomplete gardens, so partial beauty = 0
• Beauty: 4 × 20 + 0 × 5 = 80

Result: The maximum beauty is 85, achieved by completing 3 gardens and keeping 1 incomplete garden at 5 flowers.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by:

1. Initial sorting of the flowers array: O(n log n)
2. Creating the prefix sum array using accumulate: O(n)
3. Binary search to find initial value of i: O(log n)
4. The main loop runs at most n + 1 iterations (from i to n)
5. Inside each iteration:
   • Calculating max(target - flowers[n - x], 0): O(1)
   • Binary search loop to find the optimal position: O(log n)
   • Other operations are O(1)

Therefore, the overall time complexity is O(n log n) + O(n) × O(log n) = O(n log n).

Space Complexity: O(n)

The space complexity comes from:

1. The prefix sum array s created by accumulate: O(n)
2. Other variables (ans, i, l, r, mid, x, y, cost) use constant space: O(1)

Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling the Case When All Gardens Become Complete

The Pitfall: When calculating the partial beauty component, if all gardens become complete (i.e., num_complete == n), there are no incomplete gardens left. The code tries to binary search on an empty range with right = n - num_complete - 1 = -1, which causes incorrect behavior. The binary search loop condition left < right with left = 0, right = -1 immediately exits, and right = -1 is used to determine partial_level = 0. While this happens to give the correct result, it's based on coincidental behavior rather than explicit handling.

Why It Happens: The algorithm doesn't explicitly check if there are any incomplete gardens remaining before attempting to optimize their minimum flower count.

Solution: Add an explicit check for when all gardens are complete:

# After calculating newFlowers for this configuration
if num_complete == n:
    # All gardens are complete, no partial component
    beauty_score = num_complete * full
    max_beauty = max(max_beauty, beauty_score)
    continue

# Only perform binary search if there are incomplete gardens
left, right = 0, n - num_complete - 1
# ... rest of the binary search logic

2. Integer Overflow in Cost Calculation

The Pitfall: When calculating flowers[mid] * (mid + 1) - prefix_sum[mid + 1], the multiplication can cause integer overflow for large values, especially in languages with fixed integer sizes. Even in Python (which has arbitrary precision), this can lead to performance issues with very large numbers.

Why It Happens: The cost calculation involves multiplying potentially large flower counts by the number of gardens, which can exceed typical integer limits.

Solution: Check for potential overflow or use appropriate data types:

# Add bounds checking or use careful calculation
cost_to_level = flowers[mid] * (mid + 1) - prefix_sum[mid + 1]
if cost_to_level > newFlowers:
    right = mid - 1
    continue

3. Incorrect Handling of Already Complete Gardens

The Pitfall: When a garden at position n - num_complete already has target or more flowers, the code correctly calculates max(target - flowers[n - num_complete], 0) which gives 0. However, if not careful with the iteration bounds, you might try to "complete" gardens that are already complete, wasting the iteration.

Why It Happens: The initial count of gardens_already_full finds how many gardens are already at or above target, but the loop still processes these configurations.

Solution: Ensure the loop starts from the correct position and handles the initial state properly:

# More explicit handling
for num_complete in range(gardens_already_full, n + 1):
    if num_complete > gardens_already_full:
        # Only need to add flowers if we're completing more than already complete
        flowers_needed = max(target - flowers[n - num_complete], 0)
        newFlowers -= flowers_needed

4. Not Resetting newFlowers Between Iterations

The Pitfall: The code modifies newFlowers in each iteration by subtracting the cost to complete gardens. If not careful, this modification persists across iterations, causing incorrect calculations for subsequent configurations.

Why It Happens: The variable is being reused and modified in place without proper restoration.

Solution: Use a temporary variable for each iteration:

for num_complete in range(gardens_already_full, n + 1):
    remaining_flowers = newFlowers  # Create a copy for this iteration
  
    if num_complete > 0:
        flowers_needed = max(target - flowers[n - num_complete], 0)
        remaining_flowers -= flowers_needed
  
    if remaining_flowers < 0:
        break
  
    # Use remaining_flowers for the rest of the calculations