LeetCode 2234 - Maximum Total Beauty of the Gardens

LeetCode Problem 2234

Difficulty: 🔴 Hard
Topics: Array, Two Pointers, Binary Search, Greedy, Sorting, Enumeration, Prefix Sum

Solution

Problem Understanding

In this problem, we are given several gardens, where flowers[i] represents how many flowers are already planted in the i-th garden. We are also given a limited number of additional flowers, newFlowers, that we may distribute among the gardens.

The goal is to maximize the total beauty score after planting at most newFlowers flowers.

A garden becomes complete if it contains at least target flowers. Every complete garden contributes full beauty points.

Gardens that are not complete are considered incomplete. Among all incomplete gardens, we take the minimum flower count and multiply it by partial. That contributes additional beauty.

The final beauty formula is:

• (number of complete gardens) * full
• plus (minimum flowers among incomplete gardens) * partial

If every garden becomes complete, then there are no incomplete gardens, and the partial contribution becomes 0.

The important detail is that flowers can only be added, never removed.

The constraints are very large:

• Up to 10^5 gardens
• newFlowers can be as large as 10^10

This immediately rules out brute-force distribution strategies. We need an efficient algorithm, likely around O(n log n).

Several edge cases are important:

• Some gardens may already be complete initially.
• It may be optimal not to complete every garden.
• It may be better to maximize the minimum incomplete garden value instead of creating additional complete gardens.
• If all gardens become complete, the partial contribution disappears.
• Gardens with flower counts already greater than or equal to target should effectively be capped at target, because extra flowers beyond target provide no additional benefit.

The main challenge is balancing two competing objectives:

• Completing more gardens for full points
• Raising the minimum incomplete garden value for partial points

Approaches

Brute Force Approach

A brute-force strategy would try every possible way to distribute newFlowers across all gardens.

For each distribution, we would:

1. Compute how many gardens become complete.
2. Find the minimum value among incomplete gardens.
3. Calculate the resulting beauty.
4. Track the maximum result.

This approach is obviously correct because it explores every possible allocation.

However, it is completely infeasible.

Even if we only considered whether each flower goes into one of n gardens, the number of possibilities grows exponentially. With newFlowers up to 10^10, exhaustive search is impossible.

A slightly better brute-force approach could enumerate how many gardens become complete and then try all ways to maximize the incomplete minimum. But even that becomes too slow without additional optimization.

Key Insight

The crucial observation is that complete gardens and incomplete gardens can be handled separately.

Suppose we decide that exactly k gardens will be complete.

Then:

• We can greedily choose the cheapest gardens to complete.
• The remaining gardens stay incomplete.
• Among incomplete gardens, we want to maximize their minimum value.

This transforms the problem into:

1. Enumerate the number of complete gardens.
2. Use remaining flowers to maximize the minimum incomplete garden value.

Another key observation is that for incomplete gardens, the optimal strategy is to raise smaller gardens evenly. This is a classic prefix-equalization problem that can be solved efficiently with sorting and prefix sums.

Binary search can then determine the highest achievable minimum incomplete value.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(n)	Tries all flower distributions
Optimal	O(n log n)	O(n)	Uses sorting, prefix sums, greedy enumeration, and binary search

Algorithm Walkthrough

Step 1: Cap all gardens at target

Any flowers beyond target do not matter because a garden is already complete.

So we replace:

flowers[i] = min(flowers[i], target)

This simplifies later calculations.

Step 2: Sort the gardens

Sorting allows us to:

• Efficiently determine cheapest gardens to complete
• Efficiently equalize smaller incomplete gardens
• Use prefix sums for fast range cost computation

Step 3: Build a prefix sum array

We compute:

prefix[i] = sum of flowers[0:i]

This lets us calculate how many flowers are needed to raise a range of gardens to a chosen level in constant time.

Step 4: Compute completion costs from the right

The cheapest way to create complete gardens is to complete the gardens already closest to target.

We iterate from largest to smallest garden and calculate cumulative completion cost.

For example:

cost to complete flowers[i]
= target - flowers[i]

We maintain the total flowers needed to complete the largest k gardens.

Step 5: Enumerate number of complete gardens

For every possible number k of complete gardens:

1. Compute flowers needed to complete them.
2. If cost exceeds newFlowers, skip.
3. Otherwise, use remaining flowers to maximize incomplete minimum.

Step 6: Binary search the best incomplete minimum

Suppose the incomplete gardens are:

flowers[0:m-1]

We want the highest value x < target such that all incomplete gardens can be raised to at least x.

Using binary search:

• For each candidate x
• Find how many gardens are below x
• Compute cost to raise them
• Check if cost fits remaining flowers

Step 7: Compute beauty

For each configuration:

beauty = complete_gardens * full + incomplete_minimum * partial

Track the maximum.

Why it works

The algorithm works because:

• Completing gardens greedily from the largest values minimizes completion cost.
• For incomplete gardens, maximizing the minimum value is always achieved by leveling smaller gardens upward evenly.
• Sorting ensures both operations can be performed optimally.
• Enumerating all possible counts of complete gardens guarantees we do not miss the optimal balance between full and partial contributions.

Python Solution

from typing import List
import bisect

class Solution:
    def maximumBeauty(
        self,
        flowers: List[int],
        newFlowers: int,
        target: int,
        full: int,
        partial: int
    ) -> int:

        n = len(flowers)

        flowers = [min(x, target) for x in flowers]
        flowers.sort()

        prefix = [0] * (n + 1)

        for i in range(n):
            prefix[i + 1] = prefix[i] + flowers[i]

        # cost_complete[k] = flowers needed to make
        # the largest k gardens complete
        cost_complete = [0] * (n + 1)

        for k in range(1, n + 1):
            idx = n - k
            cost_complete[k] = (
                cost_complete[k - 1]
                + (target - flowers[idx])
            )

        def max_partial_value(end_index: int, remaining: int) -> int:
            """
            We consider flowers[0:end_index+1] as incomplete gardens.
            Return the maximum achievable minimum value.
            """

            if end_index < 0:
                return 0

            left = flowers[0]
            right = target - 1

            best = left

            while left <= right:
                mid = (left + right) // 2

                pos = bisect.bisect_left(
                    flowers,
                    mid,
                    0,
                    end_index + 1
                )

                needed = mid * pos - prefix[pos]

                if needed <= remaining:
                    best = mid
                    left = mid + 1
                else:
                    right = mid - 1

            return best

        answer = 0

        for complete_count in range(n + 1):

            complete_cost = cost_complete[complete_count]

            if complete_cost > newFlowers:
                continue

            remaining = newFlowers - complete_cost

            incomplete_end = n - complete_count - 1

            partial_value = max_partial_value(
                incomplete_end,
                remaining
            )

            total_beauty = (
                complete_count * full
                + partial_value * partial
            )

            answer = max(answer, total_beauty)

        return answer

The implementation begins by capping all gardens at target, because any value larger than target behaves identically for scoring purposes.

The array is then sorted, enabling efficient greedy operations and binary searches.

The prefix sum array allows fast calculation of the number of flowers required to raise multiple gardens to a chosen level.

The cost_complete array precomputes how many flowers are needed to make the largest k gardens complete. Since the largest gardens require the fewest additional flowers, this is always optimal.

The helper function max_partial_value performs a binary search for the best achievable minimum incomplete garden value. For a candidate value mid, it computes how many flowers are needed to raise all smaller gardens to at least mid.

Finally, we enumerate every possible number of complete gardens and compute the best beauty achievable for that choice.

Go Solution

package main

import (
	"sort"
)

func maximumBeauty(flowers []int, newFlowers int64, target int, full int, partial int) int64 {
	n := len(flowers)

	for i := 0; i < n; i++ {
		if flowers[i] > target {
			flowers[i] = target
		}
	}

	sort.Ints(flowers)

	prefix := make([]int64, n+1)

	for i := 0; i < n; i++ {
		prefix[i+1] = prefix[i] + int64(flowers[i])
	}

	costComplete := make([]int64, n+1)

	for k := 1; k <= n; k++ {
		idx := n - k
		costComplete[k] = costComplete[k-1] +
			int64(target-flowers[idx])
	}

	maxPartialValue := func(endIndex int, remaining int64) int64 {
		if endIndex < 0 {
			return 0
		}

		left := flowers[0]
		right := target - 1

		best := int64(left)

		for left <= right {
			mid := (left + right) / 2

			pos := sort.Search(
				endIndex+1,
				func(i int) bool {
					return flowers[i] >= mid
				},
			)

			needed := int64(mid*pos) - prefix[pos]

			if needed <= remaining {
				best = int64(mid)
				left = mid + 1
			} else {
				right = mid - 1
			}
		}

		return best
	}

	var answer int64 = 0

	for completeCount := 0; completeCount <= n; completeCount++ {

		completeCost := costComplete[completeCount]

		if completeCost > newFlowers {
			continue
		}

		remaining := newFlowers - completeCost

		incompleteEnd := n - completeCount - 1

		partialValue := maxPartialValue(
			incompleteEnd,
			remaining,
		)

		totalBeauty := int64(completeCount*full) +
			partialValue*int64(partial)

		if totalBeauty > answer {
			answer = totalBeauty
		}
	}

	return answer
}

The Go implementation follows the same structure as the Python version.

The most important difference is integer handling. Since newFlowers may reach 10^10, all cumulative sums and beauty calculations use int64.

Go does not provide a built-in bisect_left, so sort.Search is used for binary searching the first index with value at least mid.

Slices are used naturally in place of Python lists, and prefix sums are stored in an int64 slice to avoid overflow.

Worked Examples

Example 1

flowers = [1,3,1,1]
newFlowers = 7
target = 6
full = 12
partial = 1

Step 1: Sort

[1,1,1,3]

Step 2: Prefix sums

Index	Prefix Sum
0	0
1	1
2	2
3	3
4	6

Step 3: Completion costs

Complete Gardens	Cost
0	0
1	3
2	8
3	13
4	18

Only 0 or 1 complete garden are feasible.

Case: 1 complete garden

Complete the garden with 3.

Need 3 flowers
Remaining = 4

Incomplete gardens:

[1,1,1]

We binary search the highest minimum value.

Try 2:

Need 3 flowers
Possible

Try 3:

Need 6 flowers
Too expensive

Best partial value:

2

Beauty:

1 * 12 + 2 * 1 = 14

Maximum answer:

14

Example 2

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

Step 1: Cap and sort

[2,3,4,5]

Step 2: Completion costs

Complete Gardens	Cost
0	0
1	0
2	1
3	3
4	6

Case: 3 complete gardens

We spend:

3 flowers

Remaining:

7

Incomplete gardens:

[2]

We can raise it to:

4

but not to 5, otherwise it becomes complete.

Beauty:

3 * 2 + 4 * 6
= 6 + 24
= 30

This is optimal.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting plus binary searches
Space	O(n)	Prefix sums and helper arrays

Sorting dominates the runtime with O(n log n) complexity.

For each possible count of complete gardens, we perform a binary search over possible partial values. Since both dimensions are logarithmic, the overall complexity remains efficient enough for n = 10^5.

The extra memory comes from prefix sums and completion-cost arrays.

Test Cases

sol = Solution()

# Provided examples
assert sol.maximumBeauty([1,3,1,1], 7, 6, 12, 1) == 14
assert sol.maximumBeauty([2,4,5,3], 10, 5, 2, 6) == 30

# Already complete gardens
assert sol.maximumBeauty([5,5,5], 1, 5, 10, 3) == 30

# Cannot complete any garden
assert sol.maximumBeauty([1,1,1], 1, 10, 100, 5) == 10

# Single garden
assert sol.maximumBeauty([1], 10, 5, 7, 3) == 7

# Partial beauty more valuable than full
assert sol.maximumBeauty([1,1,1], 6, 5, 1, 10) == 40

# Full beauty more valuable
assert sol.maximumBeauty([1,2,3], 10, 4, 100, 1) == 300

# Large newFlowers
assert sol.maximumBeauty([1,2,3], 10000000000, 5, 10, 2) == 30

# Gardens exceeding target initially
assert sol.maximumBeauty([10,10,1], 2, 5, 7, 4) == 18

# No incomplete gardens after operations
assert sol.maximumBeauty([4,4], 2, 5, 8, 3) == 16

# Edge case with zero useful partial
assert sol.maximumBeauty([1,1], 8, 5, 10, 1) == 20

Test Summary

Test	Why
[1,3,1,1]	Verifies the first official example
[2,4,5,3]	Verifies the second official example
Already complete gardens	Ensures initial complete gardens handled correctly
Cannot complete any garden	Tests partial-only optimization
Single garden	Validates smallest input size
Partial dominates	Ensures algorithm prefers incomplete optimization
Full dominates	Ensures algorithm prefers complete gardens
Huge newFlowers	Tests large-number handling
Initial values above target	Verifies capping behavior
All gardens complete	Ensures partial contribution becomes zero
Extra flowers unused	Confirms at-most constraint handled correctly

Edge Cases

One important edge case occurs when all gardens can become complete. In this situation, there are no incomplete gardens, so the partial contribution must become zero. A buggy implementation might incorrectly add a partial score anyway. The solution handles this naturally because the helper function returns 0 when there are no incomplete gardens.

Another tricky case occurs when some gardens already exceed target. Since values beyond target provide no additional benefit, failing to cap them can distort prefix sums and completion costs. The implementation explicitly replaces every value with min(flowers[i], target) before processing.

A third important edge case happens when partial is much larger than full. In such situations, the optimal strategy may intentionally leave one garden incomplete while maximizing its minimum value. Greedy strategies that always try to maximize complete gardens will fail here. By enumerating every possible number of complete gardens, the algorithm correctly considers both possibilities.

A final subtle edge case appears with extremely large newFlowers. Since newFlowers may be as large as 10^10, using normal 32-bit integers can overflow in several languages. The Go implementation therefore uses int64 for all cumulative calculations and beauty computations.