Maximize the Beauty of the Garden - Problem

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 i^th 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.

Input & Output

Example 1 — Basic Case

$ Input: flowers = [1,3,2,1,4]

› Output: 8

💡 Note: We can create a valid garden using flowers at indices 0 and 3 (both have beauty 1). The garden includes flowers [1,3,2,1] with total beauty = 1+3+2+1 = 7. Actually, we want the maximum, so we check all possibilities and find that keeping [1,3,2,1] gives us 7.

Example 2 — Multiple Options

$ Input: flowers = [2,4,2,4]

› Output: 12

💡 Note: We have two options: garden with first/last flower = 2 gives sum 2+4+2+4 = 12, or garden with flowers at indices 1,3 (value 4) gives sum 4+2+4 = 10. Maximum is 12.

Example 3 — No Valid Garden

$ Input: flowers = [1,2,3,4]

› Output: 0

💡 Note: No two flowers have the same beauty value, so we cannot create a valid garden. Return 0.

Constraints

2 ≤ flowers.length ≤ 10⁴
-10⁴ ≤ flowers[i] ≤ 10⁴

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 f Meta 8 Apple 6

The key insight is that for any valid garden, we need matching flowers at the boundaries. The optimal approach uses prefix sums with hash map to efficiently find the maximum sum segment between first and last occurrences of each flower value. Time: O(n), Space: O(n).

Common Approaches

✓ Frequency Count

⏱️ Time: N/A Space: N/A

Optimized

⏱️ Time: N/A Space: N/A

Brute Force - Try All Pairs

⏱️ Time: O(n³) Space: O(1)

For each possible starting position, find all flowers with the same beauty value that could serve as the ending position. Calculate the sum of all flowers between each valid pair and keep track of the maximum.

Prefix Sum with Hash Map

⏱️ Time: O(n) Space: O(n)

Build prefix sum array for O(1) range sum queries. Use hash map to store first and last occurrence of each beauty value. For each unique value, calculate the sum of the segment between its first and last occurrence.

Two-Pass Hash Map Optimization

⏱️ Time: O(n) Space: O(k)

First pass identifies all flowers that have duplicates. Second pass calculates the maximum beauty by tracking running sums between first and last occurrences of matching flowers, without storing full prefix sum array.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int flowers[100000];

int maximizeBeauty(int* flowers, int flowersSize) {
    if (flowersSize < 2) return 0;
    
    int maxBeauty = 0;
    
    // Try all pairs of positions with same values
    for (int i = 0; i < flowersSize; i++) {
        for (int j = i + 1; j < flowersSize; j++) {
            if (flowers[i] == flowers[j]) {
                // Calculate sum from i to j (inclusive)
                int currentSum = 0;
                for (int k = i; k <= j; k++) {
                    currentSum += flowers[k];
                }
                if (currentSum > maxBeauty) {
                    maxBeauty = currentSum;
                }
            }
        }
    }
    
    return maxBeauty;
}

int main() {
    char line[1000000];
    if (!fgets(line, sizeof(line), stdin)) {
        return 0;
    }
    
    // Remove newline if present
    line[strcspn(line, "\n")] = 0;
    
    // Parse array format [1,2,3,4]
    int flowersSize = 0;
    
    // Find the opening bracket
    char* start = strchr(line, '[');
    if (!start) return 0;
    start++;
    
    // Find the closing bracket
    char* end = strchr(start, ']');
    if (!end) return 0;
    *end = '\0';
    
    // Parse numbers
    char* ptr = start;
    while (*ptr) {
        // Skip whitespace and commas
        while (*ptr == ' ' || *ptr == ',') ptr++;
        if (*ptr == '\0') break;
        
        // Parse number (handle negative numbers)
        char* endptr;
        int num = (int)strtol(ptr, &endptr, 10);
        if (ptr == endptr) break; // No number found
        
        flowers[flowersSize++] = num;
        ptr = endptr;
    }
    
    int result = maximizeBeauty(flowers, flowersSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen