# LeetCode 2012. Sum of Beauty in the Array

## Description

https://leetcode.com/problems/sum-of-beauty-in-the-array/

You are given a 0-indexed integer array `nums`. For each index `i` (`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`.

Example 1:

```Input: nums = [1,2,3]
Output: 2
Explanation: For each index i in the range 1 <= i <= 1:
- The beauty of nums equals 2.
```

Example 2:

```Input: nums = [2,4,6,4]
Output: 1
Explanation: For each index i in the range 1 <= i <= 2:
- The beauty of nums equals 1.
- The beauty of nums equals 0.
```

Example 3:

```Input: nums = [3,2,1]
Output: 0
Explanation: For each index i in the range 1 <= i <= 1:
- The beauty of nums equals 0.
```

Constraints:

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

## Explanation

To get a score of 2, nums[i] has to be greater than all numbers before it and has to be smaller than all numbers after it.

To get a score of 1, nums[i] just needs to be greater than the previous number and smaller than the next number

We can use dynamic programming to track the max numbers at each index position from left to right and the minimum numbers at each index position from right to left for a better computing efficiency.

## Python Solution

``````class Solution:
def sumOfBeauties(self, nums: List[int]) -> int:

sum_of_beauty = 0

max_nums = [None for i in range(len(nums))]
max_nums = nums

for i in range(1, len(nums)):
max_nums[i] = max(max_nums[i -1], nums[i])

min_nums = [None for i in range(len(nums))]
min_nums[len(nums) - 1] = nums[len(nums) - 1]

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

for i in range(1, len(nums) - 1):
max_left = max_nums[i - 1]
min_right = min_nums[i + 1]

beauty = 0

if nums[i] > max_left and nums[i] < min_right:
beauty = 2
elif nums[i] > nums[i - 1] and nums[i] < nums[i + 1]:
beauty = 1

sum_of_beauty += beauty

return sum_of_beauty``````
• Time Complexity: O(N).
• Space Complexity: O(N).