⚡ Fast & Clean Java 🧼 | 💯 O(n) Two-Pass Solution | 🚀 Beats 80%+
IntuitionThis problem could be solved by prefix array approach. However, we might not require two prefix arrays, it can be done using a single prefix array. The
# Intuition

This problem could be solved by prefix array approach. However, we might not require two prefix arrays, it can be done using a single prefix array. The prefix array can be used to track the maximum from left to right and while implementing our actual logic, we can start from the right end towards the left. We can store the minimum in a single variable to keep a track of the minimum element towards the right of an element. It would be used to check if the element at arr[j] is smaller than the smallest element towards its right, i.e., for all the values of k in arr[k].
# Approach

To efficiently calculate the sum of beauties for each element, I used a two-pass strategy:

1.	First Pass (Left to Right):
I built a lMax array where lMax[i] stores the maximum value from the beginning up to index i. This helps in checking if the current element is greater than all elements to its left.

2.	Second Pass (Right to Left):
I maintained a variable rMin to keep track of the minimum value from the end up to the current index. This helps in checking if the current element is smaller than all elements to its right.

3.	Final Pass:
For each element (excluding the first and last), I checked:
	•	If it’s strictly greater than all elements on its left and strictly smaller than all elements on its right → add 2 to the beauty.
	•	Else if it’s greater than its previous element and smaller than the next → add 1 to the beauty.


# Complexity
- Time complexity:
O(n)

- Space complexity:
O(n)
# Code
```java []
class Solution {
    public int sumOfBeauties(int[] nums) {
        int lMax[] = new int[nums.length];
        lMax[0] = nums[0];

        for(int i = 1, j=nums.length-2 ; i < nums.length ; i++, j--){
            lMax[i] = Math.max(lMax[i-1], nums[i]);
        }

        int rMin = nums[nums.length-1];
        int beautyCount = 0;

        for(int i = nums.length-2 ; i >=1 ; i--){
            if(nums[i] > lMax[i-1] && nums[i] < rMin)
                beautyCount += 2;
            else if(nums[i] > nums[i-1] && nums[i] < nums[i+1])
                beautyCount += 1;

            rMin = Math.min(rMin, nums[i]);
        }
        return beautyCount;
    }
}
```
['Java']