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[1] 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[1] equals 1.
- The beauty of nums[2] 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[1] 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[0] = nums[0]

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).