{x}
blog image

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

Solution Explanation: Sum of Beauty in the Array

This problem asks us to calculate the sum of "beauty" scores for elements in an array, where the beauty score depends on the element's relationship to its neighbors. The solution utilizes a two-pass approach for efficiency:

1. Preprocessing (Right Minimum):

  • A right array is created. right[i] stores the minimum value found in the subarray nums[i:] (from index i to the end). This is computed in a single pass from right to left. This preprocessing step allows us to efficiently check the condition nums[i] < nums[k] for all k > i in the main loop.

2. Traversal and Beauty Calculation:

  • The code iterates through the array nums from index 1 to n-2 (inclusive), where n is the length of the array. For each element nums[i]:
    • It maintains a l variable (initially nums[0]) which stores the maximum value encountered so far in nums[0] to nums[i-1]. This is updated after each iteration.
    • Condition 1 (Beauty = 2): It checks if l < nums[i] < right[i+1]. If true, this means nums[i] is greater than all elements to its left and smaller than all elements to its right, fulfilling the first condition for beauty score 2.
    • Condition 2 (Beauty = 1): If condition 1 is false, it checks if nums[i-1] < nums[i] < nums[i+1]. If true, this signifies a local peak (but not a global one, as condition 1 is false). This awards a beauty score of 1.
    • Beauty = 0: If neither condition is met, the beauty score for nums[i] is 0.
    • The beauty score is added to the ans variable.

Time Complexity: O(n) - The algorithm consists of a single pass for preprocessing and a single pass for calculating beauty scores.

Space Complexity: O(n) - An extra array right of size n is used for storing minimum values.

Code Examples:

The provided code snippets in Python, Java, C++, Go, and TypeScript all follow this two-pass approach. They differ slightly in syntax but share the same core logic. The min and max functions are used extensively for comparison and update operations.

Example Walkthrough (Python):

Let's consider the example nums = [2, 4, 6, 4].

  1. Preprocessing:

    • right will be [4, 4, 4, 4] (since 4 is the minimum in the subarrays [4, 4], [4,4], [4] , [4]).

  2. Traversal:

    • i = 1: l = 2, nums[i] = 4, right[i+1] = 4. The condition 2 < 4 < 4 is false. The condition 2 < 4 < 6 is true. ans becomes 1. l updates to max(2, 4) = 4.
    • i = 2: l = 4, nums[i] = 6, right[i+1] = 4. The condition 4 < 6 < 4 is false. ans remains 1. l updates to max(4,6) = 6.

The function returns ans = 1.

This efficient two-pass approach avoids nested loops, making the solution optimal in terms of time complexity. The use of the right array cleverly optimizes the right-side comparison.