🔥Use prefix AND/OR suffix array (full intuition included)
IntuitionThe first beauty condition is difficult to calculate, the second condition is pretty easy to check in O(1) time. Let's consider the first condition:If
# Intuition
The first beauty condition is difficult to calculate, the second condition is pretty easy to check in $O(1)$ time. Let's consider the first condition:

If we naively iterate over all $j$ and all $k$ for each $i$, time complexity will be $O(n^2)$ ($n$ steps for each index $i$)

> Let number at index $i$ be $num$

What if we knew maximum number to the left of $num$ (say $\text{maxLeft}$) and minimum number to the right of $num$, say $\text{minRight}$?

> Then we can calculate first condition simply by checking if maxLeft < num < minRight

We can calculate maxLeft and minRight using prefix and suffix arrays. But we only need to compute one of them, as ***one of them*** can be computed in $O(1)$ space by storing a variable and updating it while traversing the array from any one direction

# Complexity
- Time complexity:
$$O(n)$$ for two passes of the array of size $n$

- Space complexity:
$$O(n)$$ for either the prefix or suffix array

# Code
```cpp []
class Solution {
public:
    int sumOfBeauties(vector<int>& nums) {
        int maxLeft = 0;
        int n = nums.size();
        vector<int> minRight(n);
        // minRight[j] = smallest number to the right of index j

        minRight[n - 1] = INT_MAX; 

        for (int i = n - 2; i >= 0; i--) {
            minRight[i] = min(minRight[i + 1], nums[i + 1]);
        }

        int beauty = 0;
        for (int i = 1; i < n - 1; i++) {
            int num = nums[i];
            maxLeft = max(maxLeft, nums[i - 1]);
            if (maxLeft < num && num < minRight[i]) {
                beauty += 2;
            } else if (nums[i - 1] < num && num < nums[i + 1]) {
                beauty++;
            }
        }

        return beauty;
    }
};
```
['Array', 'Suffix Array', 'Prefix Sum', 'C++']