Sum of Beauty in the Array - Practice Coding Problems

Sum of Beauty in the Array - Problem

Array Medium

You are given a 0-indexed integer array nums. For each index i (where 1 <= i <= nums.length - 2), the beauty of nums[i] equals:

2, if nums[j] < nums[i] < nums[k] for all 0 <= j < i and for all i < k <= nums.length - 1.
1, if nums[i - 1] < nums[i] < nums[i + 1] and the previous condition is not satisfied.
0, if none of the previous conditions holds.

Return the sum of beauty of all nums[i] where 1 <= i <= nums.length - 2.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3]

› Output: 2

💡 Note: Only middle element is nums[1] = 2. Check: nums[0] < nums[1] < nums[2] → 1 < 2 < 3 ✓. Beauty = 1. Sum = 1.

Example 2 — Multiple Elements

$ Input: nums = [2,4,6,4]

› Output: 1

💡 Note: Middle elements: nums[1] = 4, nums[2] = 6. nums[1]: 2 < 4 < 6 ✓ (beauty 1). nums[2]: 4 < 6 > 4 ✗ (beauty 0). Sum = 1 + 0 = 1.

Example 3 — Maximum Beauty

$ Input: nums = [3,2,4,2,4]

› Output: 4

💡 Note: nums[1] = 2: all left [3] > 2 ✗, neighbors 3 > 2 < 4 ✗ (beauty 0). nums[2] = 4: all left [3,2] < 4 ✓, all right [2,4] ≤ 4 ✗, neighbors 2 < 4 > 2 ✗ (beauty 0). nums[3] = 2: neighbors 4 > 2 < 4 ✓ (beauty 1). Sum = 0 + 0 + 1 = 1.

Constraints

3 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array with elements to check for beauty

Beauty Calculation

Check each middle element for beauty conditions

Sum Result

Total sum of all beauty values

Key Takeaway

🎯 Key Insight: Pre-compute prefix maximums and suffix minimums to check beauty conditions in O(1) time per element

Asked in

G Google 25 M Microsoft 18

The key insight is to pre-compute maximum values to the left and minimum values to the right of each element, allowing O(1) beauty checks. Best approach uses prefix/suffix arrays with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Prefix/Suffix Maximum Optimization	O(n)	O(n)	Pre-compute maximum values to left and minimum values to right for efficient checking
Brute Force	O(n³)	O(1)	For each middle element, check all elements to its left and right

Prefix/Suffix Maximum Optimization — Algorithm Steps

Pre-compute leftMax[i] = maximum element in nums[0...i-1]
Pre-compute rightMin[i] = minimum element in nums[i+1...n-1]
For each middle element, check beauty conditions using pre-computed arrays
Sum up all beauty values

Visualization

Tap to expand

Step-by-Step Walkthrough

Pre-compute Arrays

leftMax[i] = max in nums[0...i-1], rightMin[i] = min in nums[i+1...n-1]

Quick Beauty Check

Use pre-computed values: leftMax[i] < nums[i] < rightMin[i]

Sum Results

Add beauty values for each valid middle element

Code -

solution.c — C

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

int solution(int* nums, int n) {
    if (n < 3) return 0;
    
    // Pre-compute leftMax[i] = max element in nums[0...i-1]
    int* leftMax = (int*)malloc(n * sizeof(int));
    leftMax[0] = INT_MIN;
    for (int i = 1; i < n; i++) {
        leftMax[i] = (leftMax[i-1] > nums[i-1]) ? leftMax[i-1] : nums[i-1];
    }
    
    // Pre-compute rightMin[i] = min element in nums[i+1...n-1]
    int* rightMin = (int*)malloc(n * sizeof(int));
    rightMin[n-1] = INT_MAX;
    for (int i = n-2; i >= 0; i--) {
        rightMin[i] = (rightMin[i+1] < nums[i+1]) ? rightMin[i+1] : nums[i+1];
    }
    
    int totalBeauty = 0;
    
    for (int i = 1; i < n-1; i++) {
        // Check for beauty 2: leftMax[i] < nums[i] < rightMin[i]
        if (leftMax[i] < nums[i] && nums[i] < rightMin[i]) {
            totalBeauty += 2;
        }
        // Check for beauty 1: nums[i-1] < nums[i] < nums[i+1]
        else if (nums[i-1] < nums[i] && nums[i] < nums[i+1]) {
            totalBeauty += 1;
        }
    }
    
    free(leftMax);
    free(rightMin);
    return totalBeauty;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing of [1,2,3] format
    int nums[1000];
    int n = 0;
    char* ptr = line + 1; // Skip [
    
    while (*ptr && *ptr != ']') {
        if (*ptr == ',' || *ptr == ' ') {
            ptr++;
            continue;
        }
        nums[n++] = atoi(ptr);
        while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Three passes through the array: one for leftMax, one for rightMin, one for beauty calculation

✓ Linear Growth

Space Complexity

O(n)

Two arrays of size n to store leftMax and rightMin values

⚡ Linearithmic Space

32.0K 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/Suffix Maximum Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler