#2012

Medium

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Sum of Beauty in the Array

Calculate the sum of beauty for array elements using prefix and suffix tracking to optimize evaluation across indices efficiently.

array

Problem Statement

Given a 0-indexed integer array nums, compute the beauty of each element nums[i] for indices 1 to nums.length - 2. The beauty rules are: assign 2 if nums[i] is strictly greater than all previous elements and strictly smaller than all following elements, assign 1 if nums[i] is greater than the immediate previous element and smaller than the immediate next element, otherwise assign 0.

Return the total sum of beauty for all valid indices. For example, given nums = [1,2,3], the beauty of nums[1] is 2, so the output is 2. Constraints: 3 <= nums.length <= 105 and 1 <= nums[i] <= 105.

Examples

Example 1

Input: nums = [1,2,3]

Output: 2

For each index i in the range 1 <= i <= 1:

The beauty of nums[1] equals 2.

Example 2

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

Output: 1

For each index i in the range 1 <= i <= 2:

The beauty of nums[1] equals 1.
The beauty of nums[2] equals 0.

Example 3

Input: nums = [3,2,1]

Output: 0

For each index i in the range 1 <= i <= 1:

The beauty of nums[1] equals 0.

Constraints

3 <= nums.length <= 105
1 <= nums[i] <= 105

Solution Approach

Prefix and Suffix Arrays

Compute a prefix maximum array and a suffix minimum array to quickly evaluate if nums[i] meets the strict beauty condition for 2 without scanning each subarray repeatedly.

Single Pass Evaluation

Iterate from index 1 to nums.length - 2 and check nums[i] against prefix maximum and suffix minimum for beauty 2, and simple adjacent comparisons for beauty 1, accumulating the total sum.

Optimization Considerations

Avoid recalculating max/min values by precomputing prefix/suffix arrays, ensuring O(n) time and O(n) space complexity, which scales efficiently for large arrays.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each element is processed once with precomputed prefix and suffix arrays. Space complexity is O(n) due to storing the prefix maximums and suffix minimums for all elements.

What Interviewers Usually Probe

Candidate tries nested loops instead of prefix/suffix optimization.
Candidate misses strict versus adjacent comparison distinctions for beauty evaluation.
Candidate overlooks edge indices, focusing only on middle array elements.

Common Pitfalls or Variants

Common pitfalls

Using O(n^2) nested loops leading to timeout on large arrays.
Confusing beauty 2 with beauty 1 conditions and miscounting.
Failing to precompute prefix/suffix arrays, recalculating maxima/minima repeatedly.

Follow-up variants

Compute sum of beauty for a sliding window within the array.
Modify beauty rules to consider k previous and next elements instead of immediate neighbors.
Calculate maximum possible total beauty for arrays with arbitrary integer ranges.

FAQ

What is the key strategy to solve Sum of Beauty in the Array efficiently?

Use prefix maximum and suffix minimum arrays to evaluate each element's beauty without redundant subarray scans.

Can I use nested loops to check beauty conditions?

Nested loops are inefficient for large arrays and may lead to timeouts; prefix/suffix arrays are recommended.

How do I handle the edge indices when calculating beauty?

Only indices from 1 to nums.length - 2 are valid; skip the first and last elements.

What is the difference between beauty 1 and beauty 2 in this array problem?

Beauty 2 requires strict global comparisons with all previous and following elements, while beauty 1 only requires adjacent element comparison.

Does GhostInterview help identify failure modes in array-driven solutions?

Yes, it highlights common mistakes such as miscounting beauty or missing prefix/suffix optimization opportunities.

terminal

Solution

Solution 1: Preprocessing Right Minimum + Traversing to Maintain Left Maximum

We can preprocess the right minimum array $right$, where $right[i]$ represents the minimum value in $nums[i..n-1]$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class Solution:
    def sumOfBeauties(self, nums: List[int]) -> int:
        n = len(nums)
        right = [nums[-1]] * n
        for i in range(n - 2, -1, -1):
            right[i] = min(right[i + 1], nums[i])
        ans = 0
        l = nums[0]
        for i in range(1, n - 1):
            r = right[i + 1]
            if l < nums[i] < r:
                ans += 2
            elif nums[i - 1] < nums[i] < nums[i + 1]:
                ans += 1
            l = max(l, nums[i])
        return ans

Continue Practicing

#2011 final value of variable after performing operations #2013 detect squares #2009 minimum number of operations to make array continuous