LeetCode Solutions Blog

Maximum Total Beauty of the Gardens

Number: 2330

Difficulty: Hard

Paid? No

Companies: Intuit

Problem Description

You are given several gardens with an initial number of flowers in each. You can add up to newFlowers additional flowers. A garden is complete if it has at least target flowers. The total beauty is calculated as:

(number of complete gardens) * full +
(minimum number of flowers among incomplete gardens) * partial (if there is any incomplete garden), and your goal is to maximize this total beauty under the constraint of at most newFlowers being planted.

Key Insights

Sort the gardens to separate those that are already complete (flowers[i] ≥ target) from incomplete ones.
Cap incomplete gardens’ flower counts at target (i.e. only consider filling them up to target-1, because reaching target makes them complete).
Use prefix sums on the sorted incomplete gardens to quickly calculate the cost to raise a segment to a certain minimum value.
Use binary search to determine the highest achievable minimum value for a given number of remaining additional flowers when not turning all gardens complete.
Iterate over the possible number of gardens to make complete, distributing the remaining newFlowers to maximize the minimum value among the rest.

Space and Time Complexity

Time Complexity: O(n log n)
Space Complexity: O(n)

Solution

The approach starts by sorting the gardens and separating those that already have target or more flowers from the incomplete ones. For the incomplete ones, we cap the flower count to target-1 because any garden reaching target becomes complete and should be considered separately.

A prefix sum array is built for the incomplete gardens to allow efficient queries of the cost to raise gardens to a particular minimum level. Then, for each possible count of gardens we might turn to complete (by investing enough newFlowers), we use binary search to determine the maximum possible minimum value that can be achieved among the remaining incomplete gardens. We compute the total required newFlowers using the prefix sum array and check feasibility.

By iterating over all possibilities (making 0 to all incomplete gardens complete) and also considering the case when all gardens are complete, we keep track of the maximum total beauty.

This solution uses sorting, prefix sums, and binary search as the main techniques, along with some greedy choices in distribution.

Code Solutions

def maximumBeauty(flowers, newFlowers, target, full, partial):
    # Separate complete and incomplete gardens
    complete = sum(1 for f in flowers if f >= target)
    incomplete = [min(f, target - 1) for f in flowers if f < target]
    
    # If there are no incomplete gardens, beauty is simply complete * full.
    if not incomplete:
        return complete * full
    
    # Sort incomplete gardens for efficient prefix sum calculations.
    incomplete.sort()
    n = len(incomplete)
    
    # Build prefix sum array for incomplete gardens.
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + incomplete[i]
    
    # Function to check maximum achievable minimum value among first index gardens 
    # given available additional flowers cost. Returns the maximum x such that cost to raise
    # all these gardens to x does not exceed flowers_cost.
    def can_achieve(flowers_cost, count):
        # Binary search on the value x (minimum value possible)
        lo, hi = incomplete[0], target - 1
        while lo < hi:
            mid = (lo + hi + 1) // 2
            # Find number of gardens that are below mid using binary search on sorted list.
            # We want index where garden value < mid.
            import bisect
            pos = bisect.bisect_left(incomplete, mid, 0, count)
            # Cost to raise all gardens [0, pos) up to mid.
            cost = mid * pos - prefix[pos]
            if cost <= flowers_cost:
                lo = mid
            else:
                hi = mid - 1
        return lo
    
    ans = 0
    # Try every possibility: turning some suffix of incomplete gardens into complete.
    # i gardens from the incomplete portion will be turned complete.
    # j is the count of gardens that remain incomplete among the incomplete gardens.
    # Because we can convert some gardens among incomplete to complete, 
    # we iterate for complete_converted from 0 to len(incomplete)
    for complete_converted in range(0, len(incomplete) + 1):
        # Use newFlowers to fill the last complete_converted gardens to target.
        # The rest remain incomplete and will have a minimum value 
        # at most (target - 1).
        remaining_flowers = newFlowers
        # Cost to fill the last complete_converted gardens:
        if complete_converted > 0:
            # We use the suffix of incomplete array, which is the most expensive to fill.
            # For each garden that we convert, cost = target - current_value.
            # Since incomplete is sorted in increasing order, the largest cost come from the last ones.
            # Compute cost for the last complete_converted gardens.
            cost_to_complete = 0
            for j in range(complete_converted):
                cost_to_complete += (target - incomplete[-1 - j])
            if cost_to_complete > remaining_flowers:
                continue
            remaining_flowers -= cost_to_complete
        
        # Number of gardens that remain incomplete.
        incomplete_count = len(incomplete) - complete_converted
        if incomplete_count <= 0:
            # if no incomplete, then answer might simply be (complete + complete_converted) * full.
            ans = max(ans, (complete + complete_converted) * full)
        else:
            # Calculate maximum achievable minimum value for the remaining incomplete_count gardens.
            current_min = can_achieve(remaining_flowers, incomplete_count)
            ans = max(ans, (complete + complete_converted) * full + current_min * partial)
    
    return ans

# Example usage:
print(maximumBeauty([1,3,1,1], 7, 6, 12, 1))  # Expected output: 14
print(maximumBeauty([2,4,5,3], 10, 5, 2, 6))    # Expected output: 30