Skip to main content
Talentd

Maximum Total Beauty of the Gardens - Solution & Explanation

HardArrayTwo PointersBinary SearchGreedy24 min readAsked at: Intuit
Practice this problem

Problem Statement

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:

  • The number of complete gardens multiplied by full.
  • The minimum number of flowers in any of the incomplete gardens multiplied by 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 <= 105
  • 1 <= flowers[i], target <= 105
  • 1 <= newFlowers <= 1010
  • 1 <= full, partial <= 105

Approach Overview

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.

Approach 1: Greedy Strategy with Sorting

This approach uses sorting and a greedy-like strategy to maximize the total beauty. First, sort the gardens by the number of flowers they currently have. Then, try to maximize the number of gardens that can become complete by using the available newFlowers. Once you have attempted to maximize complete gardens, distribute remaining flowers to maximize the minimum flowers in incomplete gardens.

In this solution, we first sort the array to ease the calculation of complete gardens. We then attempt to completely fill as many gardens as possible to maximize full beauty. Post that, if flowers are left, we use them to maximize partial beauty. By using sorting and a backward approach, we efficiently distribute flowers to maximize beauty.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1), apart from input storage.

Try this approach in the editor →

Approach 2: Enumeration + Binary Search

We note that if the number of flowers in a garden is already greater than or equal to target, then this garden is already a perfect garden and cannot be changed. For imperfect gardens, we can plant more flowers to make them perfect gardens.

Let's enumerate how many gardens will eventually become perfect gardens. Suppose initially there are x perfect gardens, then we can enumerate in the range [x, n]. Which imperfect gardens should we choose to become perfect gardens? In fact, we should choose the gardens with more flowers so that the remaining flowers can be used to increase the minimum value of the imperfect gardens. Therefore, we sort the array flowers.

Next, we enumerate the number of perfect gardens x. The current garden to become a perfect garden is target[n-x], and the number of flowers needed is max(0, target - flowers[n - x]).

We update the remaining flowers newFlowers. If it is less than 0, it means we can no longer make more gardens perfect, so we stop the enumeration.

Otherwise, we perform a binary search in the range [0,..n-x-1] to find the maximum index of the imperfect gardens that can be turned into perfect gardens. Let the index be l, then the number of flowers needed is cost = flowers[l] times (l + 1) - s[l + 1], where s[i] is the sum of the first i numbers in the flowers array. If we can still increase the minimum value, we calculate the increase \frac{newFlowers - cost}{l + 1}, and ensure that the final minimum value does not exceed target-1. That is, the minimum value y = min(flowers[l] + \frac{newFlowers - cost}{l + 1}, target - 1). Then the beauty value of the garden is x times full + y times partial. The answer is the maximum of all beauty values.

The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the flowers array.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Strategy with Sorting

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1), apart from input storage.

Enumeration + Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Flower DistributionO(n^2) or worseO(1)Useful only for understanding scoring logic or very small inputs
Greedy with Sorting + Binary SearchO(n log n)O(n)Optimal solution for large constraints and interview settings

Video Solution

2234. Maximum Total Beauty of the Gardens || Leetcode Weekly Contest 288 || Leetcode 2234 • Bro Coders • 2,784 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Maximum Total Beauty of the Gardens easy or hard?
Maximum Total Beauty of the Gardens is classified as a Hard problem on LeetCode with an acceptance rate around 30%. The difficulty comes from combining greedy reasoning, prefix sum optimization, and binary search while carefully managing flower distribution.
Maximum Total Beauty of the Gardens Python/Java solution
Python and Java implementations typically follow the same pattern: sort the array, compute prefix sums, iterate over possible counts of fully completed gardens, and apply binary search to maximize the minimum value among partial gardens. The overall complexity remains O(n log n).
How to solve Maximum Total Beauty of the Gardens in O(n log n)?
First sort the gardens and cap values at the target. Precompute prefix sums to calculate the cost of raising smaller gardens. Iterate over how many gardens you convert to full, and for the remaining gardens use binary search to find the highest achievable minimum value within the remaining flower budget.
What is the best approach for Maximum Total Beauty of the Gardens?
The best approach uses a greedy strategy with sorting and binary search. Sort the gardens, decide how many to make fully complete, and use prefix sums plus binary search to maximize the minimum value among remaining gardens. This reduces the search space and achieves O(n log n) time complexity.
Is Maximum Total Beauty of the Gardens asked at Google/Amazon/Meta?
Hard greedy and optimization problems like this frequently appear in interviews at companies such as Google, Amazon, and Meta. Variants that combine sorting, greedy allocation, and binary search are common in senior-level algorithm rounds.
What data structure is used in Maximum Total Beauty of the Gardens?
The main data structures are arrays and prefix sums. Sorting organizes the gardens by flower count, while prefix sums allow efficient computation of the cost to raise multiple gardens to a certain level. Binary search is then applied over possible minimum values.
What is the time complexity of Maximum Total Beauty of the Gardens?
The optimal solution runs in O(n log n) time due to sorting and binary search operations. Prefix sums allow constant-time range cost calculations when raising garden flower counts. Space complexity is O(n) for storing sorted arrays and prefix sums.

Ready to solve this problem?

Practice Maximum Total Beauty of the Gardens with our built-in code editor and test cases.

Practice on FleetCode
Previous

Split Array Largest Sum