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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Beauty in the Array

Number: 2138

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given a 0-indexed integer array nums, for each index i (1 <= i <= nums.length - 2), define the beauty of nums[i] as follows:

  • Beauty equals 2 if for every 0 <= j < i and for every i < k <= nums.length - 1, it holds that nums[j] < nums[i] < nums[k].
  • Beauty equals 1 if the above condition is not met but nums[i - 1] < nums[i] < nums[i + 1] holds.
  • Beauty equals 0 otherwise. The task is to return the sum of the beauty values of all eligible indices.

Key Insights

  • Precompute prefix maximums: for each index i store the maximum value from the start up to index i.
  • Precompute suffix minimums: for each index i store the minimum value from index i to the end.
  • For each eligible index i, check the first condition by comparing nums[i] with the prefix maximum (from i-1) and the suffix minimum (from i+1). If satisfied, add 2.
  • Otherwise, check the adjacent condition (nums[i-1] < nums[i] < nums[i+1]) and if satisfied, add 1.
  • Use O(n) time and O(n) space to precompute these arrays, ensuring an efficient solution.

Space and Time Complexity

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

Solution

We solve the problem by first precomputing two arrays: prefixMax and suffixMin.

  • prefixMax[i] holds the maximum value from index 0 to i.
  • suffixMin[i] holds the minimum value from index i to the end of the array.

When iterating through every eligible index (from 1 to nums.length - 2), we check:

  1. If prefixMax[i-1] < nums[i] < suffixMin[i+1]. If this holds, the beauty is 2.
  2. Otherwise, if nums[i-1] < nums[i] < nums[i+1] holds, the beauty is 1.
  3. If neither condition holds, the beauty is 0.

The key trick is the use of precomputed arrays to quickly determine these conditions in constant time for each index, thus reducing the overall complexity per index from O(n) to O(1).

Code Solutions

# Function to compute the sum of beauty values in the array.
def sumOfBeauty(nums):
    n = len(nums)
    # Precompute prefix maximums:
    prefixMax = [0] * n
    prefixMax[0] = nums[0]
    for i in range(1, n):
        prefixMax[i] = max(prefixMax[i - 1], nums[i])
        
    # Precompute suffix minimums:
    suffixMin = [0] * n
    suffixMin[n - 1] = nums[n - 1]
    for i in range(n - 2, -1, -1):
        suffixMin[i] = min(suffixMin[i + 1], nums[i])
        
    result = 0
    # Iterate through each eligible index:
    for i in range(1, n - 1):
        if prefixMax[i - 1] < nums[i] < suffixMin[i + 1]:
            result += 2
        elif nums[i - 1] < nums[i] < nums[i + 1]:
            result += 1
    return result

# Example usage:
# nums = [2, 4, 6, 4]
# print(sumOfBeauty(nums))  # Expected output: 1
← Back to All Questions