Watch 5 video solutions for Maximum Total Beauty of the Gardens, a hard level problem involving Array, Two Pointers, Binary Search. This walkthrough by Bro Coders has 2,719 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Alice is a caretaker of n gardens and she wants to plant flowers to maximize the total beauty of all her gardens.
You are given a 0-indexed integer array flowers of size n, where flowers[i] is the number of flowers already planted in the ith garden. Flowers that are already planted cannot be removed. You are then given another integer newFlowers, which is the maximum number of flowers that Alice can additionally plant. You are also given the integers target, full, and partial.
A garden is considered complete if it has at least target flowers. The total beauty of the gardens is then determined as the sum of the following:
full.partial. If there are no incomplete gardens, then this value will be 0.Return the maximum total beauty that Alice can obtain after planting at most newFlowers flowers.
Example 1:
Input: flowers = [1,3,1,1], newFlowers = 7, target = 6, full = 12, partial = 1 Output: 14 Explanation: Alice can plant - 2 flowers in the 0th garden - 3 flowers in the 1st garden - 1 flower in the 2nd garden - 1 flower in the 3rd garden The gardens will then be [3,6,2,2]. She planted a total of 2 + 3 + 1 + 1 = 7 flowers. There is 1 garden that is complete. The minimum number of flowers in the incomplete gardens is 2. Thus, the total beauty is 1 * 12 + 2 * 1 = 12 + 2 = 14. No other way of planting flowers can obtain a total beauty higher than 14.
Example 2:
Input: flowers = [2,4,5,3], newFlowers = 10, target = 5, full = 2, partial = 6 Output: 30 Explanation: Alice can plant - 3 flowers in the 0th garden - 0 flowers in the 1st garden - 0 flowers in the 2nd garden - 2 flowers in the 3rd garden The gardens will then be [5,4,5,5]. She planted a total of 3 + 0 + 0 + 2 = 5 flowers. There are 3 gardens that are complete. The minimum number of flowers in the incomplete gardens is 4. Thus, the total beauty is 3 * 2 + 4 * 6 = 6 + 24 = 30. No other way of planting flowers can obtain a total beauty higher than 30. Note that Alice could make all the gardens complete but in this case, she would obtain a lower total beauty.
Constraints:
1 <= flowers.length <= 1051 <= flowers[i], target <= 1051 <= newFlowers <= 10101 <= full, partial <= 105Problem 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Flower Distribution | O(n^2) or worse | O(1) | Useful only for understanding scoring logic or very small inputs |
| Greedy with Sorting + Binary Search | O(n log n) | O(n) | Optimal solution for large constraints and interview settings |