Maximize the Beauty of the Garden - Solution & Explanation
Problem Statement
There is a garden of n flowers, and each flower has an integer beauty value. The flowers are arranged in a line. You are given an integer array flowers of size n and each flowers[i] represents the beauty of the ith flower.
A garden is valid if it meets these conditions:
- The garden has at least two flowers.
- The first and the last flower of the garden have the same beauty value.
As the appointed gardener, you have the ability to remove any (possibly none) flowers from the garden. You want to remove flowers in a way that makes the remaining garden valid. The beauty of the garden is the sum of the beauty of all the remaining flowers.
Return the maximum possible beauty of some valid garden after you have removed any (possibly none) flowers.
Example 1:
Input: flowers = [1,2,3,1,2] Output: 8 Explanation: You can produce the valid garden [2,3,1,2] to have a total beauty of 2 + 3 + 1 + 2 = 8.
Example 2:
Input: flowers = [100,1,1,-3,1] Output: 3 Explanation: You can produce the valid garden [1,1,1] to have a total beauty of 1 + 1 + 1 = 3.
Example 3:
Input: flowers = [-1,-2,0,-1] Output: -2 Explanation: You can produce the valid garden [-1,-1] to have a total beauty of -1 + -1 = -2.
Constraints:
2 <= flowers.length <= 105-104 <= flowers[i] <= 104- It is possible to create a valid garden by removing some (possibly none) flowers.
Approach Overview
Problem Overview: You are given an array flowers where each value represents the beauty of a flower. The goal is to choose two positions i and j such that flowers[i] == flowers[j] and maximize the total beauty formed by those endpoints plus positive flowers between them.
The optimal subarray always starts and ends with the same value. Flowers inside the segment only contribute if their beauty is positive. Negative flowers in the middle reduce the score, so the algorithm effectively counts only positive contributions while evaluating each matching pair.
Approach 1: Brute Force Pair Enumeration (O(n²) time, O(1) space)
Iterate over every pair of indices (i, j) where i < j. Whenever flowers[i] == flowers[j], compute the beauty by scanning the elements between them and summing only positive values. Add the two endpoint values and update the maximum result. This approach is straightforward and useful for understanding the problem constraints, but it performs a nested iteration and becomes too slow for large inputs.
Approach 2: Hash Table + Prefix Sum (O(n) time, O(n) space)
The optimized solution relies on prefix sums and a hash table to evaluate valid pairs in constant time. Maintain a prefix sum that tracks the cumulative sum of positive flower values. This lets you quickly compute the positive contribution between two indices.
For each value v, store the minimum baseline expression derived from earlier occurrences of v. When the same value appears again, you can instantly calculate the beauty of the segment ending at the current index using the prefix sum and the stored baseline. A hash map keeps track of these best candidates while scanning the array once.
The key insight: instead of explicitly examining every pair, convert the beauty formula into a prefix-based expression and store the best prior state for each flower value. Each step performs constant-time arithmetic and a hash lookup, reducing the entire problem to a single pass through the array.
Recommended for interviews: The hash table + prefix sum solution is the expected approach. Interviewers want to see that you recognize the repeated-endpoint pattern, transform the scoring formula using prefix sums, and use a hash map to track the best prior occurrence. Mentioning the brute force first shows you understand the baseline, but implementing the O(n) solution demonstrates strong algorithmic optimization skills.
Solution
We use a hash table d to record the first occurrence of each aesthetic value, and a prefix sum array s to record the sum of the aesthetic values before the current position. If an aesthetic value v appears at positions i and j (where i \lt j), then we can get a valid garden [i+1,j], whose aesthetic value is s[i] - s[j + 1] + v times 2. We use this value to update the answer. Otherwise, we record the current position i of the aesthetic value in the hash table d. Next, we update the prefix sum. If the aesthetic value v is negative, we treat it as 0.
After traversing all the aesthetic values, we can get the answer.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of flowers.
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Enumeration | O(n²) | O(1) | Small inputs or when explaining the baseline logic in interviews |
| Prefix Sum + Direct Range Calculation | O(n²) | O(n) | When prefix sums simplify range sums but pair enumeration still exists |
| Hash Table + Prefix Sum (Optimal) | O(n) | O(n) | General case for large arrays; single-pass solution expected in interviews |
Video Solution
1788. Maximize the Beauty of the Garden (Leetcode Hard) • Programming Live with Larry • 249 views views
Watch 3 more video solutions →Frequently Asked Questions
Is Maximize the Beauty of the Garden easy or hard?
Maximize the Beauty of the Garden Python/Java solution
How to solve Maximize the Beauty of the Garden in O(n)?
What is the best approach for Maximize the Beauty of the Garden?
Is Maximize the Beauty of the Garden asked at Google/Amazon/Meta?
What data structure is used in Maximize the Beauty of the Garden?
What is the time complexity of Maximize the Beauty of the Garden?
Ready to solve this problem?
Practice Maximize the Beauty of the Garden with our built-in code editor and test cases.
Practice on FleetCode