Problem Description

In this problem, we are provided with a 0-indexed integer array nums. We need to determine the "beauty" for each element nums[i] at positions i from 1 to nums.length - 2, according to the following rules:

• The beauty is 2 if nums[i] is greater than all preceding elements nums[j] where j < i, and less than all succeeding elements nums[k] where k > i.
• The beauty is 1 if nums[i] is greater than the immediate preceding element nums[i - 1] and less than the immediate succeeding element nums[i + 1], but does not satisfy the condition for beauty 2.
• The beauty is 0 if none of the above conditions is satisfied.

Our goal is to calculate the sum of beauty for all such nums[i].

Intuition

The solution builds on the key observation that to find the beauty of an index i, it suffices to determine the maximum element to the left of i and the minimum element to the right of i. This leads us to an efficient way to evaluate the beauty for each index.

The approach is as follows:

1. Create two additional arrays, lmx and rmi, to record the maximum element observed from the beginning up to i - 1 and the minimum element observed from the end down to i + 1.
2. Iterate through the nums array from left to right, populating lmx by recording the maximum value seen so far.
3. Iterate through the nums array from right to left, populating rmi with the minimum value seen so far.
4. Now, traverse the array again and for each i (from 1 to nums.length - 2), check the following:
   • If lmx[i] < nums[i] < rmi[i], add 2 to the answer since nums[i] satisfies the condition for beauty 2.
   • Else if nums[i - 1] < nums[i] < nums[i + 1] and the first condition is not satisfied, add 1 to the answer, marking beauty 1.
5. Sum the beauty values calculated for each i to get the final answer.

Solution Approach

To implement the solution, we follow these steps, making use of sequential iterations and auxiliary space for the arrays needed to keep track of maximum and minimum boundaries:

1. Initialization:

   • Calculate the length n of the array nums.
   • Initialize two arrays lmx and rmi of size n to keep track of the left maximum and right minimum values, respectively. lmx[i] will store the maximum value from the start of the array to index i - 1, and rmi[i] will store the minimum value from the end of the array to index i + 1.
   • lmx is initially filled with 0 because there is no number before the start of the array.
   • rmi is filled with a very large number, 100001, to ensure that any real number in the array nums will be less than this placeholder value.

2. Populate lmx:

   • Iterate through nums from left to right starting from index 1 up to n - 1.
   • Update lmx[i] such that it holds the maximum value seen up to nums[i - 1]. This is done using the formula lmx[i] = max(lmx[i - 1], nums[i - 1]).

3. Populate rmi:

   • Iterate through nums from right to left starting from index n - 2 down to 0.
   • Update rmi[i] such that it holds the minimum value seen from nums[i + 1] to the end of the array. The formula used here is rmi[i] = min(rmi[i + 1], nums[i + 1]).

4. Calculate the total beauty:

   • Initialize a variable ans to hold the sum of beauty scores.
   • Iterate through the elements of nums from index 1 to n - 2 (inclusive).
   • Check if the beauty of nums[i] is 2 by comparing if lmx[i] < nums[i] < rmi[i]. If this condition is true, increment ans by 2.
   • Else if nums[i] does not qualify for a beauty of 2, check if it is greater than the element to its left and less than the element to its right (i.e., check if nums[i - 1] < nums[i] < nums[i + 1]). If true, increment ans by 1.
   • If neither condition is satisfied, the beauty for that element is 0, so ans remains the same.

5. Return the result:

   • After the loop completes, ans contains the sum of beauty for all nums[i], and we return this value.

The main data structures used in this solution are the arrays lmx and rmi for dynamic programming, which store computed values that can be used to determine the beauty of each element efficiently. The algorithm makes use of max() and min() functions for comparisons, and a single pass through the array (ignoring the separate passes for lmx and rmi initializations) to calculate the sum of beauty. This approach ensures that we have all the necessary information to evaluate the beauty of each element without using nested loops, which would result in a higher computational complexity.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Consider the integer array nums = [1, 2, 3, 4, 2].

Step 1: Initialization

• n = 5 (length of nums)
• Initialize lmx = [0, 0, 0, 0, 0] and rmi = [100001, 100001, 100001, 100001, 100001]

Step 2: Populate lmx

• Starting from i = 1, iterate to i = 4:
  • lmx[1] = max(0, nums[0]) = 1
  • lmx[2] = max(1, nums[1]) = 2
  • lmx[3] = max(2, nums[2]) = 3
  • lmx[4] = max(3, nums[3]) = 4
• Now lmx = [0, 1, 2, 3, 4]

Step 3: Populate rmi

• Starting from i = 3, iterate to i = 0:
  • rmi[3] = min(100001, nums[4]) = 2
  • rmi[2] = min(2, nums[3]) = 2
  • rmi[1] = min(2, nums[2]) = 2
  • rmi[0] = min(2, nums[1]) = 2
• Now rmi = [2, 2, 2, 2, 100001]

Step 4: Calculate the total beauty

• Initialize ans = 0
• For i = 1 to n - 2:
  • For i = 1:
    • lmx[1] is 1, nums[1] is 2, rmi[1] is 2.
    • nums[1] is greater than lmx[1] but not less than rmi[1], so check next condition.
    • nums[0] is 1, nums[1] is 2, nums[2] is 3. It satisfies nums[0] < nums[1] < nums[2], so add 1 to ans.
  • For i = 2:
    • lmx[2] is 2, nums[2] is 3, rmi[2] is 2.
    • nums[2] does not satisfy any beauty conditions, so ans stays the same.
  • For i = 3:
    • lmx[3] is 3, nums[3] is 4, rmi[3] is 2.
    • nums[3] is greater than both lmx[3] and rmi[3], so it adds nothing to ans.
• The final value of ans after the loop is 1.

Step 5: Return the result

The result, which is the sum of beauty for all nums[i], is 1. This is the final answer to the problem.

In this particular example, the only element to contribute to the beauty sum was nums[1] with a beauty of 1.

Solution Implementation

Time and Space Complexity

Time Complexity

The given code consists of three separate for loops that are not nested. Each of these loops runs linearly with respect to the length of the input array nums, which is denoted as n.

1. The first loop initializes the lmx array, which takes O(n) time as it iterates from 1 to n-1.
2. The second loop initializes the rmi array, which also takes O(n) time as it iterates from n-2 to 0.
3. The third loop calculates the ans (answer) by iterating once again in linear time over the range from 1 to n-1, resulting in O(n) time.

When we add these up, since they are executed in sequence and not nested, the overall time complexity of the code is O(n) + O(n) + O(n), which simplifies to O(n).

Space Complexity

The space complexity of the code is due to the additional arrays lmx and rmi that are both of length n, and the space used for variables like n, i, and ans.

1. The lmx array uses O(n) space.
2. The rmi array also uses O(n) space.

Besides these arrays, only a constant amount of extra space is used for the loop indices and the ans variable. Thus, the total auxiliary space used by the algorithm is O(n) + O(n) which simplifies to O(n).

In conclusion, the time complexity of the algorithm is O(n) and the space complexity is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.