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