We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sum of Beauty in the Array

Difficulty: Medium

Problem Description

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.

Key Insights

  • The beauty of an element depends on its surrounding elements.
  • We need to check conditions for elements to the left and right of the current index.
  • Efficiently determining the maximum and minimum values to the left and right can help in evaluating the beauty conditions.
  • We can use prefix and suffix arrays to store the maximum and minimum values.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we will use two auxiliary arrays: leftMax and rightMax. The leftMax array will store the maximum value encountered from the left up to each index, and the rightMax array will store the maximum value encountered from the right. Similarly, we can also maintain leftMin and rightMin for minimum values. With this setup, we can evaluate the beauty of each element in constant time.

  1. Traverse the array to fill leftMax and leftMin.
  2. Traverse the array in reverse to fill rightMax and rightMin.
  3. For each index i, check the conditions to determine its beauty using the precomputed values.
  4. Sum the beauty values and return the result.

Code Solutions

def sumOfBeauty(nums):
    n = len(nums)
    if n < 3:
        return 0
    
    leftMax = [0] * n
    leftMin = [0] * n
    rightMax = [0] * n
    rightMin = [0] * n
    
    leftMax[0] = nums[0]
    leftMin[0] = nums[0]
    
    for i in range(1, n):
        leftMax[i] = max(leftMax[i - 1], nums[i])
        leftMin[i] = min(leftMin[i - 1], nums[i])
    
    rightMax[n - 1] = nums[n - 1]
    rightMin[n - 1] = nums[n - 1]
    
    for i in range(n - 2, -1, -1):
        rightMax[i] = max(rightMax[i + 1], nums[i])
        rightMin[i] = min(rightMin[i + 1], nums[i])
    
    beauty_sum = 0
    for i in range(1, n - 1):
        if leftMin[i - 1] < nums[i] < rightMin[i + 1] and leftMax[i - 1] < nums[i] < rightMax[i + 1]:
            beauty_sum += 2
        elif nums[i - 1] < nums[i] < nums[i + 1]:
            beauty_sum += 1
    
    return beauty_sum
← Back to All Questions