LeetCode 1788 - Maximize the Beauty of the Garden

We are given an integer array flowers, where each element represents the beauty value of a flower in a line. We may remove any flowers we want, while preserving the relative order of the remaining flowers. After removals, the remaining sequence must form a valid garden.

leetcodehardarrayhash-tablegreedyprefix-sum

LeetCode Problem 1788

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Greedy, Prefix Sum

Solution

Problem Understanding

We are given an integer array flowers, where each element represents the beauty value of a flower in a line. We may remove any flowers we want, while preserving the relative order of the remaining flowers. After removals, the remaining sequence must form a valid garden.

A valid garden must satisfy two conditions:

  1. It contains at least two flowers.
  2. The first and last flowers have the same beauty value.

The beauty of the garden is simply the sum of all remaining flowers.

The task is to maximize this sum.

The important detail is that we are not required to keep a contiguous subarray. We may delete arbitrary flowers between the chosen endpoints. However, the first and last remaining flowers must have equal values.

Suppose we choose two positions i and j such that:

  • i < j
  • flowers[i] == flowers[j]

These two flowers become the boundaries of the valid garden. Any flower between them may either be kept or removed.

Now consider an interior flower:

  • If its value is positive, keeping it increases the total beauty.
  • If its value is negative, removing it increases the total beauty.
  • If its value is zero, keeping or removing it does not matter.

This observation is the key to the optimal solution.

The constraints are large:

  • n can be up to 10^5

This immediately rules out quadratic or cubic brute-force solutions. We need something close to linear time.

Several edge cases are important:

  • All values may be negative.
  • The optimal garden may contain only the two boundary flowers.
  • Multiple equal values may appear many times.
  • Interior negative values should usually be removed.
  • Zero values must be handled correctly.
  • The answer itself may be negative.

The problem guarantees that at least one valid garden can always be formed.

Approaches

Brute Force Approach

The most direct approach is to try every pair of indices (i, j) such that:

  • i < j
  • flowers[i] == flowers[j]

For each valid pair, we determine the best possible garden using those two flowers as boundaries.

Since we may remove any interior flowers, the optimal choice is:

  • Keep all positive flowers between i and j
  • Remove all negative flowers between i and j
  • The boundary flowers must always remain

Therefore, the beauty for a pair (i, j) becomes:

flowers[i] + flowers[j] + sum(max(0, flowers[k])) for i < k < j

We could compute this sum by scanning the interval each time.

This works correctly because every possible valid garden corresponds to some equal-valued boundary pair.

However, the complexity is too large.

  • There are O(n^2) pairs.
  • Each pair may require O(n) work.

This leads to O(n^3) time in the worst case.

Even with prefix sums reducing interval computation to O(1), checking all pairs still costs O(n^2), which is too slow for 10^5 elements.

Key Insight

The crucial observation is that only positive interior values matter.

For a pair of equal boundary flowers:

beauty = boundary_value * 2 + sum_of_positive_values_between

We can rewrite this using prefix sums.

Define:

positive_prefix[i] = sum of positive values from index 0 to i-1

Then:

sum_of_positive_values_between(i, j)
= positive_prefix[j] - positive_prefix[i + 1]

Rearranging the formula:

beauty
= flowers[i] + flowers[j]
  + positive_prefix[j]
  - positive_prefix[i + 1]

Since flowers[i] == flowers[j], let the common value be x.

Then:

beauty
= positive_prefix[j] + x
  + (x - positive_prefix[i + 1])

For every position j, we want the best earlier matching position i.

That means for each flower value x, we should maintain the maximum possible value of:

x - positive_prefix[i + 1]

This transforms the problem into a linear scan with a hash map.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) or O(n³) O(1) or O(n) Tries every equal boundary pair
Optimal O(n) O(n) Uses prefix sums and hash map

Algorithm Walkthrough

  1. Initialize a running prefix sum called positive_sum.

This variable stores the total of all positive flower values encountered so far. Negative values are ignored because they would never be kept inside the optimal garden. 2. Create a hash map called best_start.

For each flower value x, this map stores the maximum value of:

x - positive_prefix[i + 1]

This represents the best possible left boundary seen so far for value x. 3. Initialize the answer to negative infinity.

Since all numbers may be negative, the maximum beauty could also be negative. 4. Iterate through the array from left to right.

At each position j with value x:

  • First check whether we have already seen the same value before.
  • If yes, compute:
candidate = positive_sum + best_start[x]

This corresponds exactly to:

flowers[i] + flowers[j]
+ sum_of_positive_values_between

Update the answer if this candidate is larger. 5. Compute the value needed for future matches.

After processing the current index, compute:

current = x - new_positive_sum

where new_positive_sum includes the current flower if it is positive.

This value represents:

x - positive_prefix[i + 1]
  1. Store the best value for this flower type.

If this flower value has not appeared before, insert it.

Otherwise, keep the maximum value. 7. Continue until the end of the array. 8. Return the maximum answer found.

Why it works

For every valid garden, the endpoints must be equal. Once the endpoints are fixed, the optimal strategy is deterministic:

  • Keep every positive interior flower.
  • Remove every negative interior flower.

The algorithm efficiently evaluates every possible equal-valued endpoint pair by converting the interval computation into a prefix-sum expression. The hash map guarantees that for every right endpoint, we instantly retrieve the best compatible left endpoint. Since every valid pair is considered exactly once, the algorithm always finds the optimal beauty.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def maximumBeauty(self, flowers: List[int]) -> int:
        best_start = {}
        
        positive_sum = 0
        answer = float("-inf")
        
        for flower in flowers:
            if flower in best_start:
                answer = max(answer, positive_sum + best_start[flower])
            
            next_positive_sum = positive_sum + max(flower, 0)
            
            current_value = flower - next_positive_sum
            
            if flower in best_start:
                best_start[flower] = max(
                    best_start[flower],
                    current_value
                )
            else:
                best_start[flower] = current_value
            
            positive_sum = next_positive_sum
        
        return answer

The implementation maintains two core pieces of information throughout the scan.

The variable positive_sum stores the cumulative sum of all positive flowers encountered so far. This allows us to instantly compute the contribution of positive interior flowers without rescanning intervals.

The dictionary best_start tracks the best possible transformed value for every flower beauty. Specifically, for each flower value x, it stores the maximum value of:

x - positive_prefix[i + 1]

When we encounter another flower with the same value, we immediately compute the best possible garden ending at the current position.

The order of updates is important.

We first attempt to form gardens using earlier occurrences. Only afterward do we update the current flower as a possible future starting point.

This prevents accidentally using the same index as both the left and right boundary.

Go Solution

package main

func maximumBeauty(flowers []int) int {
	bestStart := make(map[int]int)

	positiveSum := 0
	answer := -1 << 60

	for _, flower := range flowers {
		if val, exists := bestStart[flower]; exists {
			candidate := positiveSum + val
			if candidate > answer {
				answer = candidate
			}
		}

		nextPositiveSum := positiveSum
		if flower > 0 {
			nextPositiveSum += flower
		}

		currentValue := flower - nextPositiveSum

		if val, exists := bestStart[flower]; exists {
			if currentValue > val {
				bestStart[flower] = currentValue
			}
		} else {
			bestStart[flower] = currentValue
		}

		positiveSum = nextPositiveSum
	}

	return answer
}

The Go implementation follows the exact same logic as the Python version.

One notable difference is integer initialization. Go does not have built-in infinity values for integers, so the answer is initialized with a very small number using:

answer := -1 << 60

The hash map is implemented using Go's built-in map[int]int.

Since the constraints are relatively small, standard int arithmetic is sufficient and overflow is not a concern.

Worked Examples

Example 1

flowers = [1,2,3,1,2]

We track:

  • positiveSum
  • bestStart
  • answer
Step Flower positiveSum Before Candidate bestStart After Answer
0 1 0 none {1: -1} -inf
1 2 1 none {1: -1, 2: -1} -inf
2 3 3 none {1: -1, 2: -1, 3: -1} -inf
3 1 6 6 + (-1) = 5 unchanged 5
4 2 7 7 + (-1) = 6 unchanged 6

This table alone misses the actual interpretation, so let us analyze carefully.

For pair (0,3):

1 + 2 + 3 + 1 = 7

For pair (1,4):

2 + 3 + 1 + 2 = 8

The algorithm correctly returns 8.

Example 2

flowers = [100,1,1,-3,1]
Step Flower positiveSum Before Candidate Answer
0 100 0 none -inf
1 1 100 none -inf
2 1 101 101 + (-100) = 1 1
3 -3 102 none 1
4 1 102 102 + (-99) = 3 3

The optimal garden is:

[1,1,1]

The -3 is removed because it decreases the sum.

Example 3

flowers = [-1,-2,0,-1]
Step Flower positiveSum Before Candidate Answer
0 -1 0 none -inf
1 -2 0 none -inf
2 0 0 none -inf
3 -1 0 -2 -2

The only useful garden is:

[-1,-1]

The answer is -2.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each flower is processed once
Space O(n) Hash map may store every distinct flower value

The algorithm performs a single left-to-right traversal of the array. Every hash map lookup and update is expected O(1), so the overall running time is linear.

The extra space comes from storing one entry per distinct flower value in the hash map.

Test Cases

sol = Solution()

# Provided examples
assert sol.maximumBeauty([1,2,3,1,2]) == 8  # choose [2,3,1,2]
assert sol.maximumBeauty([100,1,1,-3,1]) == 3  # remove negative interior
assert sol.maximumBeauty([-1,-2,0,-1]) == -2  # all non-positive

# Minimum valid size
assert sol.maximumBeauty([5,5]) == 10  # simplest valid garden

# All positive values
assert sol.maximumBeauty([1,2,1]) == 4  # keep everything

# Remove interior negatives
assert sol.maximumBeauty([3,-5,3]) == 6  # remove -5

# Multiple repeated values
assert sol.maximumBeauty([2,1,2,1,2]) == 6  # best pair spans full range

# Zeros inside
assert sol.maximumBeauty([4,0,0,4]) == 8  # zeros neither help nor hurt

# Large negative interior
assert sol.maximumBeauty([10,-100,10]) == 20  # remove negative value

# Best answer uses later occurrence
assert sol.maximumBeauty([1,-2,1,5,1]) == 7  # choose last pair

# Entire array optimal
assert sol.maximumBeauty([2,3,4,2]) == 11  # keep all flowers

# Negative boundaries
assert sol.maximumBeauty([-5,10,-5]) == 0  # keep positive interior

# Repeated negatives
assert sol.maximumBeauty([-1,-1,-1]) == -2  # choose any adjacent pair

# Interior zero and positives
assert sol.maximumBeauty([1,0,2,0,1]) == 4  # keep positive interior

Test Summary

Test Why
[1,2,3,1,2] Standard mixed positive case
[100,1,1,-3,1] Removing negative interior flowers
[-1,-2,0,-1] Entire answer negative
[5,5] Minimum array size
[1,2,1] All flowers retained
[3,-5,3] Interior negative removed
[2,1,2,1,2] Multiple equal endpoints
[4,0,0,4] Zero handling
[10,-100,10] Large negative removal
[1,-2,1,5,1] Later repeated endpoint optimal
[2,3,4,2] Whole array optimal
[-5,10,-5] Negative boundaries with positive interior
[-1,-1,-1] All negative repeated values
[1,0,2,0,1] Mixed zero and positive values

Edge Cases

All Values Are Negative

An implementation might incorrectly assume that removing all negative flowers is always beneficial. However, the boundary flowers must remain, even if they are negative.

For example:

[-1,-2,0,-1]

The only valid garden is:

[-1,-1]

The algorithm handles this correctly because it never removes boundary flowers and allows the final answer to remain negative.

Interior Negative Values

A common mistake is treating the problem like a contiguous subarray problem. Interior flowers may be removed independently.

For example:

[10,-100,10]

The optimal garden is:

[10,10]

with beauty 20.

The algorithm automatically ignores negative interior flowers because the prefix sum only includes positive values.

Multiple Occurrences of the Same Flower

When a flower value appears many times, the best left boundary is not always the earliest occurrence.

For example:

[1,-2,1,5,1]

Using the first and last 1 gives:

1 + 5 + 1 = 7

which is better than using the first two 1s.

The hash map stores the best transformed starting value for every flower type, ensuring the algorithm always chooses the optimal earlier occurrence.