Maximize the Beauty of the Garden - Practice Coding Problems

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

Understanding the Visualization

Input

Array of flower beauty values

Find Matches

Identify flowers that can serve as valid boundaries

Calculate Segments

Find maximum sum between matching boundaries

Key Takeaway

🎯 Key Insight: Find all segments where first and last flowers have the same beauty value, then return the maximum sum among all such valid segments.

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

Approach	Time	Space	Notes
✓ Prefix Sum with Hash Map	O(n)	O(n)	Use prefix sums and hash map to efficiently find maximum beauty segments
Brute Force - Try All Pairs	O(n³)	O(1)	Try every possible pair of matching flowers as endpoints
Two-Pass Hash Map Optimization	O(n)	O(k)	Two-pass approach with optimized space using running sum

Prefix Sum with Hash Map — Algorithm Steps

Build prefix sum array
Find first and last occurrence of each beauty value
For each unique value, calculate segment sum using prefix sums
Return maximum sum

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Prefix Sum

Precompute cumulative sums

Find Boundaries

Track first/last occurrence of each value

Calculate Segments

Use prefix sum for O(1) range queries

Code -

solution.c — C

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

#define MAX_VAL 100000

long long solution(int* flowers, int n) {
    if (n < 2) return 0;
    
    // Build prefix sum array
    long long* prefix = (long long*)calloc(n + 1, sizeof(long long));
    for (int i = 0; i < n; i++) {
        prefix[i + 1] = prefix[i] + flowers[i];
    }
    
    // Find first and last occurrence of each value
    int* first = (int*)malloc(MAX_VAL * sizeof(int));
    int* last = (int*)malloc(MAX_VAL * sizeof(int));
    int* seen = (int*)calloc(MAX_VAL, sizeof(int));
    
    for (int i = 0; i < n; i++) {
        int val = flowers[i] + 50000; // offset for negative values
        if (!seen[val]) {
            first[val] = i;
            seen[val] = 1;
        }
        last[val] = i;
    }
    
    long long maxBeauty = 0;
    
    // For each unique value that appears at least twice
    for (int val = 0; val < MAX_VAL; val++) {
        if (seen[val] && first[val] != last[val]) {
            // Sum from first[val] to last[val] (inclusive)
            long long segmentSum = prefix[last[val] + 1] - prefix[first[val]];
            if (segmentSum > maxBeauty) {
                maxBeauty = segmentSum;
            }
        }
    }
    
    free(prefix);
    free(first);
    free(last);
    free(seen);
    
    return maxBeauty;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    // Simple JSON array parsing
    int flowers[10000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        flowers[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    long long result = solution(flowers, n);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to build prefix sum and hash map, then iterate unique values

✓ Linear Growth

Space Complexity

O(n)

Hash map stores up to n unique values, prefix sum array of size n+1

⚡ 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum with Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler