Sum of Beauty in the Array

Sum of Beauty in the Array

What is this problem about?

The "Sum of Beauty in the Array" problem asks you to calculate a "beauty score" for each element nums[i] in an array (where $1 \le i \le n-2$) based on its relationship with the rest of the array.

• A score of 2 is given if nums[i] is strictly greater than all elements to its left AND strictly smaller than all elements to its right.
• A score of 1 is given if the first condition isn't met but nums[i-1] < nums[i] < nums[i+1].
• Otherwise, the score is 0. The goal is to return the total sum of these beauty scores for all valid indices i.

Why is this asked in interviews?

Amazon frequently uses this problem to test a candidate's ability to handle array-wide constraints efficiently. The "Score 2" condition requires knowing the maximum value to the left and the minimum value to the right of every element. It's a classic problem for teaching the concept of "Pre-processing" and "Auxiliary Arrays" to avoid redundant nested loops.

Algorithmic pattern used

The pattern used is Pre-computation using Prefix Maximums and Suffix Minimums.

1. Create an array max_left where max_left[i] is the maximum of all elements from 0 to i-1.
2. Create an array min_right where min_right[i] is the minimum of all elements from i+1 to n-1.
3. Iterate from i = 1 to n-2 and check:
   • If max_left[i] < nums[i] < min_right[i], add 2.
   • Else if nums[i-1] < nums[i] < nums[i+1], add 1.

Example explanation

Array: [1, 2, 3]

• For index 1 (value 2):
  • Is it > all on left (1) and < all on right (3)? Yes. Score = 2.
• Total Sum = 2. Array: [2, 4, 6, 3]
• For index 1 (value 4):
  • Is 4 > {2} and < {6, 3}? No (4 < 3 is false).
  • Is 2 < 4 < 6? Yes. Score = 1.
• For index 2 (value 6):
  • Is 6 > {2, 4} and < {3}? No.
  • Is 4 < 6 < 3? No. Score = 0.
• Total Sum = 1.

Common mistakes candidates make

1. Inefficient re-scanning: For every index i, re-scanning the entire left and right side to find the max and min. This results in an O(N²) solution.
2. Incorrect index bounds: Only processing elements from i=1 to n-2. Forgetting the constraints on i can lead to errors.
3. Strict vs. Non-strict inequalities: Misreading "strictly greater" (>) as "greater than or equal to" (>=).

Interview preparation tip

Any time you need to compare an element against "all elements to the left" or "all elements to the right," your mind should immediately jump to pre-computing prefix/suffix arrays. This is a very common technique for optimizing array problems.