Trapping Rain water Similar Approach using prefix and postfix max and min.
IntuitionWe need to compute the sum of beauties for each element in the array (except the first and last). The beauty of an element is determined by specific co
## Intuition
We need to compute the **sum of beauties** for each element in the array (except the first and last). The beauty of an element is determined by specific conditions:
- It gets **2 points** if it is strictly greater than all elements to its left and strictly smaller than all elements to its right.
- Otherwise, it gets **1 point** if it is **greater than its previous element and smaller than its next element**.
- If none of the conditions are met, it gets **0 points**.

A brute force approach would check **all previous and next elements** for each position, but this is inefficient. Instead, we optimize using **prefix maximums and postfix minimums**.

---

## Approach
1. **Compute postfix minimums**:
   - Create an array `postfixMins[]` where `postfixMins[i]` stores the **minimum element from index `i` to the end**.
   - This helps us quickly check if `nums[i]` is smaller than all elements to its right.

2. **Iterate through the array**:
   - Maintain a **prefix maximum** (`maxi`) to track the maximum value encountered so far.
   - At each `i`, check:
     - If `nums[i] > prefixMax` **and** `nums[i] < postfixMin`, add `2` to `beautySum`.
     - Otherwise, if `nums[i] > nums[i-1]` **and** `nums[i] < nums[i+1]`, add `1` to `beautySum`.

3. **Update the prefix maximum** as we iterate.

This approach ensures that we efficiently check conditions in **O(1) per element** after preprocessing.

---

## Complexity
- **Time Complexity:**  
  - **Computing `postfixMins`**: $$O(n)$$  
  - **Iterating through `nums`**: $$O(n)$$  
  - **Total Complexity**: **$$O(2n)$$**

- **Space Complexity:**  
  - **Postfix minimums array**: $$O(n)$$  
  - **Other variables**: $$O(1)$$  
  - **Total Complexity**: **$$O(n)$$**


# Code
```cpp []
class Solution {
public:
    int sumOfBeauties(vector<int>& nums) {
        
        int n = nums.size();
        vector<int> postfixMins(n, INT_MAX);

        int mini = INT_MAX;
        for (int i = n-1; i >= 0; i--) {
            mini = min(mini, nums[i]);
            postfixMins[i] = mini;
        }

        int maxi = nums[0];
        int beautySum = 0;

        for (int i = 1; i < n-1; i++) {
            int prefixMax = maxi;
            int postfixMin = postfixMins[i+1];

            if (nums[i] > prefixMax && nums[i] < postfixMin) {
                beautySum += 2;
            }
            else if (nums[i] > nums[i-1] && nums[i] < nums[i+1]) {
                beautySum++;
            }

            maxi = max(maxi, nums[i]);
        }

        return beautySum;
    }
};
```
['Array', 'Math', 'Dynamic Programming', 'Greedy', 'Memoization', 'Prefix Sum', 'C++']