Problem Description

You are given a 0-indexed integer array nums. Your task is to calculate the "beauty" value for each element at index i where 1 <= i <= nums.length - 2 (all elements except the first and last), and return the sum of all beauty values.

The beauty of nums[i] is determined by the following rules:

1. Beauty = 2: If nums[i] is greater than ALL elements before it (indices from 0 to i-1) AND less than ALL elements after it (indices from i+1 to nums.length-1). In other words, nums[j] < nums[i] < nums[k] for all 0 <= j < i and all i < k <= nums.length - 1.

2. Beauty = 1: If the first condition is not satisfied, but nums[i] is greater than its immediate left neighbor AND less than its immediate right neighbor. That is, nums[i-1] < nums[i] < nums[i+1].

3. Beauty = 0: If neither of the above conditions is satisfied.

The goal is to calculate the beauty value for each valid index and return their sum.

For example, if an element at index i is larger than all elements to its left and smaller than all elements to its right, it contributes 2 to the total sum. If it's only larger than its immediate left neighbor and smaller than its immediate right neighbor (but not satisfying the global condition), it contributes 1. Otherwise, it contributes 0.

Intuition

To determine if an element nums[i] has beauty value 2, we need to check if it's greater than all elements to its left and less than all elements to its right. Instead of checking all left and right elements for each index (which would be inefficient), we can think about what we actually need:

• For the left side: We only need to know the maximum value among all elements before index i. If nums[i] is greater than this maximum, then it's greater than all elements to its left.

• For the right side: We only need to know the minimum value among all elements after index i. If nums[i] is less than this minimum, then it's less than all elements to its right.

This observation leads us to a key insight: we can precompute the information we need. For the right side, we can create an array right where right[i] stores the minimum value from index i to the end of the array. This can be built by traversing the array from right to left.

For the left side, we don't need a separate array. As we traverse from left to right to calculate the beauty values, we can maintain a running maximum l that represents the maximum value seen so far (before the current index).

During our main traversal, for each index i:

• We check if l < nums[i] < right[i+1] (where l is the max of all elements before i, and right[i+1] is the min of all elements after i)
• If this condition holds, the beauty is 2
• Otherwise, we check the local condition nums[i-1] < nums[i] < nums[i+1] for beauty value 1
• After checking, we update l to include the current element for the next iteration

This approach allows us to compute the answer in linear time with only one preprocessing pass and one main pass through the array.

Solution Approach

The solution implements the preprocessing and traversal strategy as follows:

Step 1: Build the Right Minimum Array

First, we create an array right where right[i] stores the minimum value from index i to the end of the array:

n = len(nums)
right = [nums[-1]] * n
for i in range(n - 2, -1, -1):
    right[i] = min(right[i + 1], nums[i])

• Initialize right array with the last element value
• Traverse from right to left (index n-2 to 0)
• For each position, right[i] = min(right[i+1], nums[i]), which gives us the minimum from current position to the end

Step 2: Traverse and Calculate Beauty Values

Now we traverse the array from left to right, maintaining the left maximum and calculating beauty values:

ans = 0
l = nums[0]  # Initialize left maximum with first element
for i in range(1, n - 1):  # Check indices 1 to n-2
    r = right[i + 1]  # Minimum of all elements after index i
  
    # Check for beauty value 2
    if l < nums[i] < r:
        ans += 2
    # Check for beauty value 1
    elif nums[i - 1] < nums[i] < nums[i + 1]:
        ans += 1
  
    # Update left maximum for next iteration
    l = max(l, nums[i])

Key Points:

• l maintains the maximum value of all elements before index i
• right[i + 1] gives us the minimum value of all elements after index i
• For beauty value 2: We check if l < nums[i] < r
• For beauty value 1: We check the local condition with immediate neighbors
• After processing each element, we update l to include the current element

Time Complexity: O(n) - We make two passes through the array
Space Complexity: O(n) - For the right array storing minimum values

Example Walkthrough

Let's walk through the solution with the array nums = [1, 3, 2, 5, 4].

Step 1: Build the Right Minimum Array

We need to build an array where right[i] stores the minimum value from index i to the end.

Starting from the right:

• right[4] = 4 (only element is 4)
• right[3] = min(4, 5) = 4 (minimum of 5 and everything after)
• right[2] = min(4, 2) = 2 (minimum of 2 and everything after)
• right[1] = min(2, 3) = 2 (minimum of 3 and everything after)
• right[0] = min(2, 1) = 1 (minimum of 1 and everything after)

So right = [1, 2, 2, 4, 4]

Step 2: Calculate Beauty Values

Now we traverse indices 1 to 3 (excluding first and last elements):

Index i = 1 (element = 3):

• Left maximum l = 1 (max of all elements before index 1)
• Right minimum r = right[2] = 2 (min of all elements after index 1)
• Check beauty = 2: Is 1 < 3 < 2? No (3 is not less than 2)
• Check beauty = 1: Is nums[0] < nums[1] < nums[2]? Is 1 < 3 < 2? No
• Beauty value = 0
• Update l = max(1, 3) = 3

Index i = 2 (element = 2):

• Left maximum l = 3 (max of all elements before index 2)
• Right minimum r = right[3] = 4 (min of all elements after index 2)
• Check beauty = 2: Is 3 < 2 < 4? No (2 is not greater than 3)
• Check beauty = 1: Is nums[1] < nums[2] < nums[3]? Is 3 < 2 < 5? No
• Beauty value = 0
• Update l = max(3, 2) = 3

Index i = 3 (element = 5):

• Left maximum l = 3 (max of all elements before index 3)
• Right minimum r = right[4] = 4 (min of all elements after index 3)
• Check beauty = 2: Is 3 < 5 < 4? No (5 is not less than 4)
• Check beauty = 1: Is nums[2] < nums[3] < nums[4]? Is 2 < 5 < 4? No
• Beauty value = 0
• Update l = max(3, 5) = 5

Total sum = 0 + 0 + 0 = 0

Let's try another example where we get non-zero beauty values: nums = [1, 2, 3, 0, 5]

Step 1: Build Right Minimum Array

• right = [0, 0, 0, 0, 5]

Step 2: Calculate Beauty Values

Index i = 1 (element = 2):

• l = 1, r = right[2] = 0
• Beauty = 2: Is 1 < 2 < 0? No
• Beauty = 1: Is 1 < 2 < 3? Yes! Beauty value = 1
• Update l = 2

Index i = 2 (element = 3):

• l = 2, r = right[3] = 0
• Beauty = 2: Is 2 < 3 < 0? No
• Beauty = 1: Is 2 < 3 < 0? No
• Beauty value = 0
• Update l = 3

Index i = 3 (element = 0):

• l = 3, r = right[4] = 5
• Beauty = 2: Is 3 < 0 < 5? No
• Beauty = 1: Is 3 < 0 < 5? No
• Beauty value = 0

Total sum = 1 + 0 + 0 = 1

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. This is because:

• The first loop iterates through the array once from right to left to build the right array, taking O(n) time
• The second loop iterates through the array once from index 1 to n-2 to calculate the sum of beauties, taking O(n) time
• All operations inside both loops (comparisons, assignments, min/max operations) take O(1) time
• Total time complexity: O(n) + O(n) = O(n)

The space complexity is O(n), where n is the length of the array nums. This is because:

• The right array is created with size n, requiring O(n) space
• Other variables (l, r, ans, i) use constant space O(1)
• Total space complexity: O(n) + O(1) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Order of Condition Checking

A critical pitfall is checking the beauty value 1 condition before the beauty value 2 condition, or not understanding that these conditions are mutually exclusive with priority given to beauty value 2.

Incorrect Implementation:

# WRONG: Checking local condition first
if nums[i - 1] < nums[i] < nums[i + 1]:
    total_beauty += 1
elif left_max < nums[i] < right_minimum:
    total_beauty += 2  # This would never execute for valid beauty-2 cases

Why it's wrong: If an element satisfies the global condition (beauty = 2), it will always also satisfy the local condition. Checking the local condition first would incorrectly assign beauty = 1 to elements that should have beauty = 2.

Correct Approach:

# Check global condition first (beauty = 2)
if left_max < nums[i] < right_minimum:
    total_beauty += 2
# Only check local condition if global fails (beauty = 1)
elif nums[i - 1] < nums[i] < nums[i + 1]:
    total_beauty += 1

2. Forgetting to Update Left Maximum

Another common mistake is forgetting to update the left_max variable after processing each element, or updating it before using it for the current element.

Incorrect Implementation:

# WRONG: Not updating left_max
for i in range(1, n - 1):
    if left_max < nums[i] < right_minimum:
        total_beauty += 2
    # Forgot to update left_max!

Correct Approach:

for i in range(1, n - 1):
    if left_max < nums[i] < right_minimum:
        total_beauty += 2
    elif nums[i - 1] < nums[i] < nums[i + 1]:
        total_beauty += 1
  
    # Must update left_max AFTER checking current element
    left_max = max(left_max, nums[i])

3. Off-by-One Errors in Right Minimum Array

Be careful with indexing when building and accessing the right minimum array.

Incorrect Implementation:

# WRONG: Using wrong index for right minimum
for i in range(1, n - 1):
    right_minimum = right_min[i]  # This includes nums[i] itself!
    if left_max < nums[i] < right_minimum:
        total_beauty += 2

Why it's wrong: right_min[i] includes nums[i] in the minimum calculation. We need the minimum of elements strictly after index i, which is right_min[i + 1].

Correct Approach:

for i in range(1, n - 1):
    right_minimum = right_min[i + 1]  # Minimum of elements AFTER index i
    if left_max < nums[i] < right_minimum:
        total_beauty += 2