Leetcode #2234: Maximum Total Beauty of the Gardens
In this guide, we solve Leetcode #2234 Maximum Total Beauty of the Gardens in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
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.
Quick Facts
- Difficulty: Hard
- Premium: No
- Tags: Greedy, Array, Two Pointers, Binary Search, Enumeration, Prefix Sum, Sorting
Intuition
The constraints hint that we can reason about two ends of the data at once, which is perfect for a two-pointer scan.
Moving one pointer at a time keeps the invariant intact and avoids nested loops.
Approach
Place pointers at the left and right ends and move them based on the comparison or target condition.
This yields a clean linear pass after any required sorting.
Steps:
- Set left and right pointers.
- Move a pointer based on the condition.
- Update the best answer while scanning.
Example
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.
Python Solution
class Solution:
def maximumBeauty(
self, flowers: List[int], newFlowers: int, target: int, full: int, partial: int
) -> int:
flowers.sort()
n = len(flowers)
s = list(accumulate(flowers, initial=0))
ans, i = 0, n - bisect_left(flowers, target)
for x in range(i, n + 1):
newFlowers -= 0 if x == 0 else max(target - flowers[n - x], 0)
if newFlowers < 0:
break
l, r = 0, n - x - 1
while l < r:
mid = (l + r + 1) >> 1
if flowers[mid] * (mid + 1) - s[mid + 1] <= newFlowers:
l = mid
else:
r = mid - 1
y = 0
if r != -1:
cost = flowers[l] * (l + 1) - s[l + 1]
y = min(flowers[l] + (newFlowers - cost) // (l + 1), target - 1)
ans = max(ans, x * full + y * partial)
return ans
Complexity
The time complexity is , and the space complexity is . The space complexity is .
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.