Four Solutions | Brute➡️Optimal | ✅Clean CPP Code✅
😊 ~ 𝙒𝙞𝙩𝙝 ❤️ 𝙗𝙮 𝙃𝙞𝙧𝙚𝙣IntuitionHello There It's Easy!
Just Take A Look At The Code And Comments Within It, You'll Get It!ApproachApproaches -
: Using Brute Force
😊 ~ 𝙒𝙞𝙩𝙝 ❤️ 𝙗𝙮 𝙃𝙞𝙧𝙚𝙣
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
***Hello There It's Easy! 
Just Take A Look At The Code And Comments Within It, You'll Get It!***

# Approach
<!-- Describe your approach to solving the problem. -->
***Approaches -
: Using Brute Force
: Avoiding Redundancy In Brute Force
: Using Time Optimization In Brute Force
: Space Optimization In Previous Approach***

***Similiar Problems: 
[Problem 1](https://leetcode.com/problems/minimum-sum-of-mountain-triplets-ii/solutions/6612689/three-solutions-bruteoptimal-clean-cpp-c-yaea/)
[Problem 2](https://leetcode.com/problems/maximum-value-of-an-ordered-triplet-ii/solutions/6611757/three-solutions-bruteoptimal-clean-cpp-c-wrff/)***

# Complexity
- ***Time complexity: Mentioned with the code***
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- ***Space complexity: Mentioned with the code***
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
**Approach 1 : Using Brute Force (TLE)**
```
class BruteForce_V1 {
public:
    // O(N^2) & O(1)
    int sumOfBeauties(vector<int>& nums) {
        int n = nums.size();
        int sumOfBeauty = 0;

        for(int i = 1; i <= n-2; ++i) {
            int maxAtLeft = nums[0];
            for(int j = 0; j < i; ++j) { // Find the maximum element lying at the left side of ith index
                maxAtLeft = max(maxAtLeft, nums[j]);
            }

            int minAtRight = nums[n - 1];
            for(int k = i+1; k < n; ++k) { // Find the minimum element lying at the right side of ith index
                minAtRight = min(minAtRight, nums[k]);
            }

            if(maxAtLeft < nums[i] && nums[i] < minAtRight) { // Calculate the sum of beauty
                sumOfBeauty += 2;
            } else if(nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
                sumOfBeauty += 1;
            }
        }

        return sumOfBeauty;
    }
};
```
**Approach 2 : Avoiding Redundancy In Brute Force (TLE)**
```
class BruteForce_V2 {
public:
    // O(N^2) & O(1)
    int sumOfBeauties(vector<int>& nums) {
        int n = nums.size();
        int sumOfBeauty = 0;

        for(int i = 1; i <= n-2; ++i) {
            int maxAtLeft = nums[0];
            int minAtRight = nums[n - 1];

            for(int j = 0; j < n; ++j) { // Find the maximum and minimum element lying at the left and right side of ith index
                if(j < i) {
                    maxAtLeft = max(maxAtLeft, nums[j]);
                } else if(j > i) {
                    minAtRight = min(minAtRight, nums[j]);
                }
            }

            if(maxAtLeft < nums[i] && nums[i] < minAtRight) { // Calculate the sum of beauty
                sumOfBeauty += 2;
            } else if(nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
                sumOfBeauty += 1;
            }
        }

        return sumOfBeauty;
    }
};
```
**Approach 3 : Time Optimization In Brute Force (Accepted)**
```
class Precomputation {
public:
    // O(3*N) & O(2*N)
    int sumOfBeauties(vector<int>& nums) {
        int n = nums.size();
        vector<int> maxAtLeft(n), minAtRight(n);

        int maxElement = nums[0];
        for(int i = 1; i < n; ++i) { // Find the maximum element lying at the left side of each index
            maxAtLeft[i] = maxElement;
            maxElement = max(maxElement, nums[i]);
        }

        int minElement = nums[n - 1];
        for(int i = n-2; i >= 0; --i) { // Find the minimum element lying at the right side of each index
            minAtRight[i] = minElement;
            minElement = min(minElement, nums[i]);
        }

        int sumOfBeauty = 0;
        for(int i = 1; i <= n-2; ++i) { // Calculate the sum of beauty
            if(maxAtLeft[i] < nums[i] && nums[i] < minAtRight[i]) {
                sumOfBeauty += 2;
            } else if(nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
                sumOfBeauty += 1;
            }
        }

        return sumOfBeauty;
    }
};
```
**Approach 4 : Space Optimization In Previous Approach (Accepted)**
```
class PrecomputationEnhanced {
public:
    // O(2*N) & O(1*N)
    int sumOfBeauties(vector<int>& nums) {
        int n = nums.size();
        vector<int> maxAtLeft(n);

        int maxElement = nums[0];
        for(int i = 1; i < n; ++i) { // Find the maximum element lying at the left side of each index
            maxAtLeft[i] = maxElement;
            maxElement = max(maxElement, nums[i]);
        }

        int minAtRight = nums[n - 1];
        int sumOfBeauty = 0;
        for(int i = n-1; i >= 0; --i) { // Find the minimum element at the right side of each index, calculate the sum of beauty
            if(i >= 1 && i <= n-2) {
                if(maxAtLeft[i] < nums[i] && nums[i] < minAtRight) {
                    sumOfBeauty += 2;
                } else if(nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) {
                    sumOfBeauty += 1;
                }
            }
            minAtRight = min(minAtRight, nums[i]);
        }

        return sumOfBeauty;
    }
};
```
𝗨𝗣𝗩𝗢𝗧𝗘 𝗜𝗙 𝗬𝗢𝗨 𝗟𝗜𝗞𝗘 𝗧𝗛𝗘 𝗦𝗢𝗟𝗨𝗧𝗜𝗢𝗡 👍
['Array', 'Prefix Sum', 'C++']